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是使用该功能可以找到的元素。
如果结构中存在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