C++ STL二分查找std::upper_bound()函数入门

前面我们学习了lower_bound()函数的学习，读者是否还记得lower_bound()函数的功能呢？对的，lower_bound()函数的功能是在指定有序范围内查找第一个不低于目标元素的元素。而本节我们会学习一个与lower_bound()函数“相反”的函数，它就是upper_bound()函数，“upper”意为“高一级的”，“bound”意为“边界”，该函数的功能是在指定有序范围内查找第一个高于（读者切勿认为是“不高于”）目标元素的元素，作用区间和lower_bound()函数一样都必须为有序区间，比如我们有一个序列{1，2，3，4，5}，我们想要查找第一个高于3的元素，所以我们找到元素4。

upper_bound()函数的语法格式为：

//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
 const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
 const T& val, Compare comp);

upper_bound(first, last,val)函数的功能是在指定有序区间[first,last)内找到第一个高于val的元素，如果找到就返回指向该元素的迭代器，否则返回容器的尾后迭代器end()。

下面我们通过代码来实操一下upper_bound(first, last,val)函数：

#include<iostream>
#include<vector>
#include<algorithm>//需包含算法头文件才能使用upper_bound()函数
using namespace std;
  
/*upper_bound(first, last，val)*/ 
void test()
{
    vector<int> v{1,2,3,4,5};
    cout << "原序列为：";
    for(auto it = v.begin();it!=v.end();++it)cout << *it << " ";
    cout << '\n';
    /*找到第一个不小于3的元素*/ 
vector<int>::iterator pos =upper_bound(v.begin(),v.end(),3);
 cout << "找到第一个高于3的元素：【" << *pos << "】\n" ;
} 
  
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

在序列{1,2,3,4,5}，第一个高于3的元素是4，输出完全符合预期。

总结：如果我们想要在指定有序区间内查找第一个高于目标元素的元素，我们最好使用upper_bound(first, last，val)函数，因为upper_bound(first, last，val)函数是基于二分查找实现的，效率比find()等线性查找函数效率高。