C++ STL lower_bound()和upper_bound()

时间:2022-03-03 07:00:22

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最大的可以插入的数组位置
C++ STL lower_bound()和upper_bound()
 
示例代码:
 1 #include <algorithm>
 2 #include <iostream>
 3 using namespace std;
 4 int main()
 5 {
 6     int a[10] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
 7     int n = 10;
 8     for(int i = 0; i < 5; i ++)
 9     {
10         int *lower = lower_bound(a, a+n, i);
11         int *upper = upper_bound(a, a+n, i);
12         cout << lower - a << ' ' << upper - a << endl;
13     }
14     return 0;
15 } 
16 /*
17 0 0
18 1 0
19 1 3
20 3 6
21 6 10
22 10 10
23 */

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

 
2、在vector上的用法
vector就相当于一个可以 长度可变的数组。当用于vector上时,需要注意以下几点:
  • 前两个参数必须是vector的迭代器
  • 函数的返回值也是迭代器
 vector的迭代器和数组的指针有点类似,比如也可以通过两个迭代器相减算出偏移量,也就是下标。
 
示例代码:
 1 #include <algorithm>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int a[10] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
 8     int n = 10;
 9     vector<int> b(a, a+10);
10     
11     for(int i = 0; i < 5; i ++)
12     {
13         vector<int>::iterator lower = lower_bound(b.begin(), b.end(), i);
14         vector<int>::iterator upper = upper_bound(b.begin(), b.end(), i);
15         cout << lower - b.begin() << ' ' << upper - b.begin() << endl;
16     }
17     return 0;
18 } 
19 /*
20 0 0
21 1 0
22 1 3
23 3 6
24 6 10
25 10 10
26 */