本文主要是介绍stl-二分找上下界，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
下面介绍两个函数用来查找一个有序序列关键字的上下界
upper_bound返回第一个大于的元素的下标；
lower_bound返回第一个大于或等于元素的下标；
代码如下：
#include<stdio.h>
#include<algorithm>
using namespace std;int main()
{int data[10] ={0,1,1,2,2,2,2,3,4,7};//upper_bound(a,b,key) 从区间a,b-1查找key,找不到返回b(注意，此时a,b是迭代器类型)int res = upper_bound(data,data+10,5) - data; //upper_bound返回第一个大于的关键字的下标； int res1 = lower_bound(data,data+10,5) - data; //lower_bound返回第一个大于或等于的关键字的下标 printf("%d %d\n",res,res1);return 0;
}lower_bound和upper_bound内部实现代码
#include<stdio.h>
int lower_bound(int* data,int l,int r,int key); //lower_bound返回第一个大于或等于关键字的下标 也就是查找下界
int upper_bound(int* data,int l,int r,int key); //upper_bound返回第一个大于关键字的下标，也就是查找上界
int main()
{int data[10] ={0,1,1,2,2,2,2,3,4,7};int res = upper_bound(data,0,9,2) ; int res1 = lower_bound(data,0,9,5) ; printf("%d %d\n",res,res1);return 0;
} int lower_bound(int* data,int l,int r,int key)
{int m = 0;while(l < r){m = (l + r) / 2;if(data[m] >= key)r = m;elsel = m + 1;} return l;
}
int upper_bound(int* data,int l,int r,int key)
{int m = 0;while(l < r){m = (l + r) / 2;if(data[m] <= key)l = m + 1;elser = m; }return l;
}二分的循环不变式：
1.关键字在区间[l,r]内
2.区间[l,r]在不断缩小
这篇关于stl-二分找上下界的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
