C++ lower_bound() 和 upper_bound() 用法

1.概述

​

lower_bound() 和 upper_bound() 包含在头文件<algorithm>中。

lower_bound()和upper_bound()都是利用二分查找的方法在一个排好序的数组中进行查找的，数组排序默认从小到大。

2.函数介绍

lower_bound()

• default : it lower_bound(it first, it last, const &val); (it 表示iterator)

• custom : it lower_bound(it first, it last, const &val, compare cmp);

  Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val. 函数返回 [first,last) 区间中不小于val的元素的迭代器指针， 如果找不到返回last。

upper_bound()

• default : it upper_bound(it first, it last, const &val); (it 表示iterator)

• custom : it upper_bound(it first, it last, const &val, compare cmp);

  Returns an iterator pointing to the first element in the range [first,last) which compares greater than val. 函数返回 [first,last) 区间中大于val的元素的迭代器指针，如果找不到返回last。

vector<int> v{1, 1, 3, 3, 3, 4};

int pos1 = lower_bound(v.begin(), v.end(), 3) - v.begin();
int pos2 = upper_bound(v.begin(), v.end(), 3) - v.begin();
cout << "pos1 : " << pos1 << endl; //pos1 : 2
cout << "pos2 : " << pos2 << endl; //pos2 : 5

int pos3 = lower_bound(v.begin(), v.end(), 1) - v.begin();
int pos4 = upper_bound(v.begin(), v.end(), 4) - v.begin();
cout << "pos3 : " << pos3 << endl; //pos3 : 0
cout << "pos4 : " << pos4 << endl; //pos4 : 6

我们可以发现：

lower_bound() 得到的结果表示：val在数组最早能插入到那个位置

upper_bound()得到的结果表示：val在数组最晚能插入到那个位置

cmp

lower_bound() 和 upper_bound()查找的数组是默认是从小到大排序的，如果我们的数组是从大到小排序的该怎么办？

一个容易想到的解决办法是我们可以先将数组逆序，然后正常查找即可。

其实我们可以使用lower_bound() 和 upper_bound()的第四个参数cmp，我们可以这样写：

bool cmp(int a, int b){
    return a > b;
}

vector<int> v{4,3,3,3,1,1};

int pos5 = lower_bound(v.begin(), v.end(), 1, cmp) - v.begin();
int pos6 = upper_bound(v.begin(), v.end(), 4, cmp) - v.begin();
cout << "pos5 : " << pos5 << endl; //pos3 : 4
cout << "pos6 : " << pos6 << endl; //pos4 : 1

当然我们也可以用greater<type>()代替 cmp，效果是一样的。

我们总结发现：

lower_bound() 在数组中找出 val的左边界， upper_bound() 在数组中找出val的右边界，而且结果正好符合[val)，左闭右开。