二分

一.什么是二分搜索？

在有界并有序的解空间内不断缩减可能存在的范围，从而得到问题最优解的答案。
只有有界闭区间才能保证缩减次数是有限的，同时也只有存在单调性才能够保证二分的使用是正确的，保证去掉的值是不合法或者不是最优解。

二.二分搜索的实现

求最有解可以转换成求满足某个条件C(x)的最大(/最小)的x

const double eps = 1e-6;

bool C(typedef x){	//判断x是否满足……条件，并返回结果
	/* ……*/ 
}

//整数二分 
int bsearch(int l,int r){
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(C(mid))	l = mid;
		else	r = mid;
	}
	return l;
}

//浮点数二分
double bsearch(double l,double r){
	while(r - l > eps){
		double mid = (l + r) / 2;
		if(C(mid))
			r = mid;
		else
			l = mid;
	}
	return l;
}

三.便捷的STL二分函数

	①返回大于或等于 val 的第一个元素位置
		lower_bound(arr,arr+n,val);
	②返回大于val 的第一个元素位置
		upper_bound(arr,arr+n,val);
	③返回的是 bool 值,是否存在这么一个数
		binary_search(arr,arr+n,val); 
	④长度为 n 的有序数组 a 中 k 的个数
 		upper_bound(a,a+n,k) - lower_bound(a,a+n,k); 
 		
    如：从长度为 n 的 a 数组中找到第一个大于等于 3 的元素的数组下标：
 		cout<<(lower_bound(a,a+n,3) - a)<<endl;