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最大的可以插入的数组位置
示例代码:
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 */