//版本一:调用operator<进行比较 template <class ForwardIterator,class StrictWeaklyCompareable> bool binary_search(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value); //版本二：调用自己定义的function object template <class ForwardIterator,class T,class StrictWeaklyCompareable> bool binary_search(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
若找到值==value的，返回true，否则返回false（if and only if [first,last)中存在一个iterator i，使得*i<value&&vale<*i（cmp(*i,value)和cmp(value,*i)）都不成立返回true）
对于RandomAccessIterator和其他的Iterator复杂度不同，advance对于RandomAccessIterator为常量，对于ForwardIterator为线性
//版本一:调用operator<进行比较 template <class ForwardIterator,class StrictWeaklyCompareable> bool lower_bound(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value); //版本二：调用自己定义的function object template <class ForwardIterator,class T,class StrictWeaklyCompareable> bool lower_bound(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
为二分查找的一种
//版本一:调用operator<进行比较 template <class ForwardIterator,class StrictWeaklyCompareable> bool upper_bound(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value); //版本二：调用自己定义的function object template <class ForwardIterator,class T,class StrictWeaklyCompareable> bool upper_bound(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
为二分查找的一种
//版本一:由iterator i，j构成的pair，i为[fisrt,last)中最远的iterator，使得[fisrt,i)中每个iterator k都满足*k<=value //j是[fisrt,last)最远的iterator，使得[fisrt,j)中每个iterator k都满足value<*k不为真，对于[i,j)中每个iterator k，满足value //<*k和*k<value都不为真 template <class ForwardIterator,class StrictWeaklyCompareable> pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value); //版本二：调用自己定义的function object template <class ForwardIterator,class T,class StrictWeaklyCompareable> pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
结合了lower_bound和upper_bound两者的返回值，返回值是一对i，j，以pair的形式返回，i是第一个可安插value的位置，j是不破坏原来顺序下最后一个可安插的位置，[i,j)中的每个元素都与value相等，所以equal_range的返回值是[first,last)的一个子区间，若range内没有任何一个元素与value等价，返回的是个空range，不破坏原来的range下只有一个位置可安插value，pair的两个元素都指向该位置
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v{1,1,3,4,5,6,6,8,9}; cout<<binary_search(v.begin(),v.end(),5)<<endl; cout<<*lower_bound(v.begin(),v.end(),2)<<endl; cout<<*upper_bound(v.begin(),v.end(),11)<<endl; typedef typename vector<int>::iterator it1; typedef typename vector<int>::iterator it2; pair<it1,it2> p=equal_range(v.begin(),v.end(),7); cout<<"i:"<<*(p.first)<<" j:"<<*(p.second)<<endl; return 0; }
binary_search,lower_bound,upper_bound,equal_range
原文：https://www.cnblogs.com/tianzeng/p/10391119.html