二分查找

二分查找有固定的模板，在不同的情况下有两种，只需要记住模板之后直接套用即可。
二分一般都是在有序的情况下，但是有些情况下使不需要有序的，我们只需要满足check(mid)，即某种性质即可。
模板1：

//定义好范围
int l,r;
while(l<r){
	int mid=l + r + 1 >> 1;
	if(check(mid)) l=mid;//如果这里是l=mid，上面的mid就需要+1
	else r=mid+1;
}
//我们最后取l或者r都是一样的，但是为了保险一般都取r，因为有的时候取l是不对的。

模板2

int l,r;
while(l<r){
	int mid=l+r>>1;
	if(check(mid)) r=mid;//因为这里是r=mid，所以不需要+1
	else l=mid-1;
}

二分练习
练习参考答案