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

前面几章，我们已经深入学习了很多查找算法，比如find()函数、find_if()函数、find_first_of()函数等，它们都是线性查找。本节我们开始其他查找方式的学习，比如lower_bound()函数、upper_bound()函数、equal_range()函数和binary_search()函数，它们都能够查找元素，只不过底层采用二分查找的方式，效率比线性查找高。本节我们进行lower_bound()函数的学习。“lower”意为“更低的”，“bound”意为“边界”，lower_bound()函数的功能是在指定范围内查找第一个不低于目标元素的元素。比如我们有一个序列{1，2，3，4，5}，我们想要查找第一个不小于3的元素，所以我们找到元素3。

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

//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
 const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
 const T& val, Compare comp);

lower_bound(first, last，val)函数的功能是在指定区间[first,last)内找到第一个不低于val的元素，如果找到就返回指向该元素的迭代器，否则返回last迭代器。

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

#include<iostream>
#include<vector>
#include<algorithm>//需包含算法头文件才能使用lower_bound()函数
using namespace std;
 
/*lower_bound(first, last)*/ 
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 =lower_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的元素是3，输出完全符合预期。

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