二分查找模板

题目：二分查找模板

代码：

public int binarySearch1(){
	int l = 区间左端点, r = 区间右端点;
    while(l<r){
    	int mid = l + r >> 1;
    	if(check(mid)) r = mid;
    	else l = mid + 1;
    }
    return r;
}
public int binarySearch2(){
	int l = 区间左端点, r = 区间右端点;
    while(l<r){
    	int mid = l + r + 1>> 1;
    	if(check(mid)) r = mid - 1;
    	else l = mid;
    }
    return r;
}

思路：

1. 循环写成while(l<r)，在退出循环时有r == l成立，就不用再判断是返回l，还是返回r了。
2. 区间[l, r]的划分有以下两种情况：
   ① 分成[l, mid]和[mid+1, r]。分别对应r = mid 和 l = mid +1;
   ② 分成[l, mid-1]和[mid, r]。分别对应l = mid 和r = mid - 1，这种情况下需要把 mid = (l + r) / 2改成 mid = (l + r + 1) / 2，否则会出现死循环，当出现死循环的时候，可以把l和r的值打印以下，看一看就清楚了，不用死记硬背。
3. 退出循环时有 r == l，如果区间 [ l , r ]内确定有解，则直接返回 l 就可以，否则还需要对l这个位置单独做一次判断。
4. 二分查找的不变量是：在区间 [ l , r ]里查找目标元素。
5. check()函数是重点，需要根据题目要求，去确定我们的二分区间，根据题目进行分析即可，不需要死记硬背，多做点题就可以掌握分析的方法。