数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ STL 中的二分查找函数（binary_search、lower_bound 和 upper_bound）
二分查找是一种搜索算法，它通过将元素与数组的中值进行比较并将数组进行划分来搜索元素。该算法会重复执行此操作，直到找到该元素。
为了对数组应用二分查找，数组必须已排序。
二分查找的时间复杂度为**对数**阶。因此，程序员除了了解二分查找的实现外，还必须了解与二分查找相关的速记方法，以减少编写该算法代码的时间。本文将讨论标准模板库 (STL) 中包含的与二分查找算法相关的函数。
lower_bound - 下界搜索返回找到元素的位置。
语法
lower_bound(start_pointer , end_pointer, element )
此处，
start_pointer 是一个指针，它保存搜索结构起点的内存位置。
end_pointer 是一个指针，它保存搜索结构终点的内存位置。
element 是要使用该函数查找的元素。
该函数返回要查找的元素的索引。
返回值可能有多个值 -
如果元素在结构中出现一次，则返回其位置。
如果元素在结构中出现多次，则返回第一个元素的位置。
如果元素不在结构中，则返回比元素大的下一个数字的位置。
任何元素的索引都是通过减去结构的基本位置来找到的。
示例
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
cout<<"The position of element 7 found using lower_bound function :";
cout<<"\nCase 1 : When element is present in array but only once ";
cout<<lower_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\nCase 2 : When element is present more than one times in the array ";
cout<<lower_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : When element is not present in the array ";
cout<<lower_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}输出
The position of element 7 found using lower_bound function : Case 1 : When element is present in array but only once 2 Case 2 : When element is present more than one times in the array 2 Case 3 : When element is not present in the array 4
upper_bound - 上界搜索返回高于传递元素的元素的位置。
语法
upper_bound(start_pointer , end_pointer, element)
此处，
start_pointer 是一个指针，它保存搜索结构起点的内存位置。
end_pointer 是一个指针，它保存搜索结构终点的内存位置。
element 是要使用该函数查找的元素。
该函数返回其值大于元素值的元素的索引。
返回值可能有多个值 -
如果元素在结构中出现一次，则返回下一个更高元素的位置。
如果元素在结构中出现多次，则返回最后一个元素的下一个元素的位置。
如果元素不在结构中，则返回比元素大的下一个数字的位置。
任何元素的索引都是通过减去结构的基本位置来找到的。
示例
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
cout<<"The position of element 7 found using upper_bound function :";
cout<<"\nCase 1 : When element is present in array but only once ";
cout<<upper_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\nCase 2 : When element is present more than one times in the array ";
cout<<upper_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : When element is not present in the array ";
cout<<upper_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}输出
The position of element 7 found using upper_bound function : Case 1 : When element is present in array but only once 3 Case 2 : When element is present more than one times in the array 4 Case 3 : When element is not present in the array 4
binary_search 是一个函数，它检查元素是否在结构中。
语法
binary_search(start_pointer , end_pointer, element)
此处，
start_pointer 是一个指针，它保存搜索结构起点的内存位置。
end_pointer 是一个指针，它保存搜索结构终点的内存位置。
element 是要使用该函数查找的元素。
如果元素存在于结构中，则函数返回 true。否则，它将返回 false。
示例
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {6, 15, 21, 27, 39, 42};
cout<<"The element to be found in the array is 21\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 21))
cout<<"The element is found";
else
cout<<"The element is not found";
cout<<"\nThe element to be found in the array is 5\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 5))
cout<<"The element is found";
else
cout<<"The element is not found";
}输出
The element to be found in the array is 21 The element is found The element to be found in the array is 5 The element is not found
4K+ 次查看
