lower_bound和upper_bound的使用方法

使用方法

刚好最近在给学弟学妹讲二分，应该是我没讲明白。。

还是写出来比较好。

lower_bound和upper_bound的头文件都是algorithm。

需要传入三个参数，数组头begin，数组尾end，以及你需要查找的数num。

在使用时，需要保证数组（容器）需要有序。

最好是递增的，因为递减需要重载，之前没讲清楚。。

递增数组

lower_bound( begin,end,num)，即在begin到end-1中查找第一个大于等于的数，并且返回该数的地址，减去begin之后，得到与begin的相对位置。

upper_bound与lower_bound使用方法相同，但是查找的是第一个大于的数，不会查找等于的。

递减数组

lower_bound( begin,end,num,greater< Type >() )，即在begin到end-1中查找第一个小于等于的数，并且返回该数的地址，减去begin之后，得到与begin的相对位置。

upper_bound与lower_bound使用方法相同，但是查找的是第一个小于的数，不会查找等于的。

greater函数头文件是functional。

注意二分的范围是begin~end-1。

具体使用

const int N = 1e5 + 5, mod = 1e9 + 7;
int num[N];

int main() {
	int n; scanf("%d",&n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}
	sort(num, num + n);							         //按从小到大排序 
	int find; scanf("%d", &find);
	int pos1 = lower_bound(num, num + n, find) - num;    //返回数组中第一个大于或等于被查找的数
	int pos2 = upper_bound(num, num + n, find) - num;    //返回数组中第一个大于被查找的数
	printf("%d %d\n", pos1, num[pos1]);
	printf("%d %d\n", pos2, num[pos2]);
	sort(num, num + 6, greater<int>());                             //按从大到小排序
	int pos3 = lower_bound(num, num + n, find, greater<int>()) - num;  //返回数组中第一个小于或等于被查找的数 
	int pos4 = upper_bound(num, num + n, find, greater<int>()) - num;  //返回数组中第一个小于被查找的数 
	printf("%d %d\n", pos3, num[pos3]);
	printf("%d %d\n", pos4, num[pos4]);
	return 0;
}