二分查找

概念要求

二分用来找边界值，例如查找最后一个小于x的数，

取中间值，每次判断是否满足条件（例如小于），如果满足就接着找，变化左边界与有边界

要求： 数组单调 这个单调并不是说数值上单调，而是满足某种性质，这种性质左边的没有，右边的有，利用这个性质就可以找到其分界点

实现

//找到最后一个小于等于x的数
int l = 0, r = len;
while(l <= r)
{
	int mid = l + r + 1 >> 1;
	if(a[mid] < x) l = mid;
	else r = mid - 1;
}
 
//第一个大于等于x的数
while(l <= r)
{
	int mid = l + r >> 1;
	if(a[mid] >= x)  r = mid;
	else l = mid + 1;
}
 
 
while(l < r){
	int mid = l + r >> 1;
	if(check(q[mid])) r = mid;
	else l = mid + 1;
}
 
while(l < r){
	int mid = l + r + 1 >> 1;
	if(check(q[mid])) l = mid;
	else r = mid - 1;
}
 

实际上是，当q[mid]满足check的时候，mid本身包含在满足性质的一边，让 r=mid或者l=mid其实是默认要找的边界是满足性质的，所以下面两个模板是找

• check检查右边性质：满足性质的第一个
• check检查左边性质：满足性质的最后一个

实现上要注意几点：

• 怎么写其实是由逻辑决定的 要找到的数如果是包含在条件里的，那么mid就包含在下一个要找的区间里
• 为了防止死循环所以在<的条件下要再加上1 设想，如果3个数，例如1 2 3 找大于2的数，第一次找2，发现不对，再找，l+r >> 1，结果还是2，进入死循环（这是由于除法的向下取整）
• 同时，while条件和 if 条件最好不要都有等于，可能会死循环