STL lower_bound函数

STL lower_bound函数算法

在 STL 中 lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。

STL lower_bound函数使用

find()、find_if()、search() 等查找函数的底层实现都采用的是顺序查找（逐个遍历）的方式，在某些场景中的执行效率并不高。例如，当指定区域内的数据处于有序状态时，如果想查找某个目标元素，更推荐使用二分查找的方法（相比顺序查找，二分查找的执行效率更高）。

幸运的是，C++ STL 标准库中还提供有 lower_bound()、upper_bound()、equal_range() 以及 binary_search() 这 4 个查找函数，它们的底层实现采用的都是二分查找的方式。

STL lower_bound函数详解

头文件

#include <algorithm>

语法

//在 [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);

参数

参数	描述
first	正向迭代器
last	正向迭代器
val	指定目标元素
comp	自定义比较规则

说明

first 和 last 都为正向迭代器，[first, last) 用于指定函数的作用范围；val 用于指定目标元素；comp 用于自定义比较规则，此参数可以接收一个包含 2 个形参（第二个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

实际上，第一种语法格式也设定有比较规则，只不过此规则无法改变，即使用 < 小于号比较 [first, last) 区域内某些元素和 val 的大小，直至找到一个不小于 val 的元素。这也意味着，如果使用第一种语法格式，则 [first,last) 范围的元素类型必须支持 < 运算符。

此外，该函数还会返回一个正向迭代器，当查找成功时，迭代器指向找到的元素；反之，如果查找失败，迭代器的指向和 last 迭代器相同。

技术细节

该函数仅适用于已排好序的序列。所谓 “已排好序”，指的是 [first, last) 区域内所有令 element<val（或者 comp(element,val)，其中 element 为指定范围内的元素）成立的元素都位于不成立元素的前面。

案例

STL lower_bound函数

使用 STL lower_bound 函数分组集合

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class mycomp 
{
public:
    bool operator()(const int& i, const int& j) 
    {
        return i>j;
    }
};
int main() 
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;	
	int a[5] = { 1,2,3,4,5 };
    int *p = lower_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;
    vector<int> myvector{ 4,5,3,1,2 };
    vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(),3,mycomp());
    cout << "*iter = " << *iter;
    cout << endl;
    return 0;
}

我们在 Linux 下使用 g++ 进行编译，具体命令如下：

g++ lower_bound.cpp -std=c++11

编译后，我们直接运行生成的二进制文件 a.out，如下图所示：

myvector 容器中存储的元素看似是乱序的，但对于元素 3 来说，大于 3 的所有元素都位于其左侧，小于 3 的所有元素都位于其右侧，且查找规则选用的是 mycomp2()，其查找的就是第一个不大于 3 的元素，因此 lower_bound() 函数是可以成功运行的。

STL lower_bound函数总结

在 STL 中 lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。