C++ STL lower_bound()和upper_bound()

lower_bound()和upper_bound()用法

---

 

1、在数组上的用法

假设a是一个 递增数组，n是数组长度，则

• lower_bound(a, a+n, x)：返回数组a[0]~a[n-1]中，【大于等于】x的数中，最小的数的指针
• upper_bound(a, a+n, x)：返回数组a[0]~a[n-1]中，【大于】x的数中，最小的数的指针

由于指针可以通过加减算偏移量，所以我们再减去a(数组名会被隐式转换成指针)，就得到了相应的下标。

 

对于lower_bound和upper_bound还有一个等价的解释。就是假设我要在a数组中插入x，然后还保持递增，那么

• lower_bound返回的是x最小的可以插入的数组位置
• upper_bound返回的是x最大的可以插入的数组位置

 

示例代码：

#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    int a[10] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
    int n = 10;
    for(int i = 0; i < 5; i ++)
    {
        int *lower = lower_bound(a, a+n, i);
        int *upper = upper_bound(a, a+n, i);
        cout << lower - a << ' ' << upper - a << endl;
    }
    return 0;
} 
/*
0 0
1 0
1 3
3 6
6 10
10 10
*/

注：lower_bound( )和upper_bound( )的前两个参数是待查范围的首尾指针(左闭右开区间，不包括尾指针)

 

2、在vector上的用法

vector就相当于一个可以 长度可变的数组。当用于vector上时，需要注意以下几点：

• 前两个参数必须是vector的迭代器
• 函数的返回值也是迭代器

 vector的迭代器和数组的指针有点类似，比如也可以通过两个迭代器相减算出偏移量，也就是下标。

 

示例代码：

#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    int a[10] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
    int n = 10;
    vector<int> b(a, a+10);
    
    for(int i = 0; i < 5; i ++)
    {
        vector<int>::iterator lower = lower_bound(b.begin(), b.end(), i);
        vector<int>::iterator upper = upper_bound(b.begin(), b.end(), i);
        cout << lower - b.begin() << ' ' << upper - b.begin() << endl;
    }
    return 0;
} 
/*
0 0
1 0
1 3
3 6
6 10
10 10
*/