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<<"使用 lower_bound 函数找到元素 7 的位置:";
cout<<"\n情况 1:当元素在数组中出现但仅一次时 ";
cout<<lower_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\n情况 2:当元素在数组中出现多次时 ";
cout<<lower_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : 当元素不在数组中时 ";
cout<<lower_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}
输出
使用 lower_bound 函数找到元素 7 的位置: 情况 1:当元素在数组中出现但仅出现一次时 2 情况 2:当元素在数组中出现多次时 2 情况 3:当元素不在数组中时 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<<"使用 upper_bound 函数找到元素 7 的位置:";
cout<<"\n情况 1:当元素在数组中存在但仅一次时 ";
cout<<upper_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\n情况 2:当元素在数组中出现多次时 ";
cout<<upper_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3:当元素不在数组中时 ";
cout<<upper_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}
输出
使用 upper_bound 函数找到元素 7 的位置: 情况 1:元素在数组中存在但仅出现一次 3 情况 2:元素在数组中出现多次 4 情况 3:元素不在数组中 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<<"要在数组中找到的元素是 21\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 21))
cout<<"元素已找到";
else
cout<<"元素未找到";
cout<<"\n数组中要查找的元素为 5\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 5))
cout<<"元素已找到";
else
cout<<"未找到元素";
}
输出
数组中要查找的元素为 21 元素已找到 数组中要查找的元素为 5 未找到元素
