二分查找由于思想简单，在经典算法中最容易被初学者忽视。
看懂了书上的一种写法后，就以为自己会了，而实际上是一看就会，一写就废。
不信的话，先来看一个问题：
找出升序数组中小于等于目标值的最大值？（数组中可能不包含目标值）
如果感觉很棘手，别着急，看完本文你能随手撸出两种不同的解法。如果你写出来了，也别着急，继续看下去，你会发现你写的不一定完美。好啦，不管怎样，看完绝对不亏，哈哈。
一、开门见山
不绕弯弯，针对问题：找出升序数组中小于等于目标值的最大值？
直接给出两种二分查找的典型写法，
第一种：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid;
}
return high; // 必须返回 high
}
第二种：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high + 1) >>> 1;
if(a[mid] > target) high = mid - 1;
else low = mid;
}
return low; // 返回 high 也可以
}
这两种写法最明显的区别是，在 while 循环里，第一种是三分支判断，第二种是两分支判断。
二分查找版，找不同游戏：
- high 的初始值，有 a.length 和 a.length-1 两种
- while 循环条件，有 low < high 和 low <= high 两种
- 取中位数，有 取左中位数 和 取右中位数 两种
- 取中位数的写法，以取左中位数为例，有 low+(high-low)/2、low+((high-low)>>1)、(low+high)>>>1（推荐这种写法）等。注意 low+high 可能溢出，最好不要写成 (low+high)/2
- low 和 high 的更新，以 low 为例，有 low = mid 和 low = mid+1 两种
- 判断分支的个数，有两分支和三分支两种。
可见二分查找的写法是多么灵活！
不过对于上面的找不同，有几点需要说明一下。
high 的初值设置和 while 循环条件有关，当循环条件为 low <= high 时，必须写 a.length-1，否则两种写法都可以。
另外，只有两分支写法需要取右中位数和边界更新为中位数（e.g. low = mid），后面会说到。
简单解释一下，为什么 (low+high)>>>1 不用担心溢出，溢出之所以出错，是因为有一部分数值进到了符号位，我们只要把符号位当成是数值位，结果就是正确的，而无符号右移，刚好就不会处理符号的问题。
二、第一种写法：三分支二分查找（推荐写法）
这种写法，除了返回值以外基本上都可以闭着眼睛写
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid;
}
由于 while 循环条件是 low <= high，所以退出循环时，low != high，至于最终是返回 low 还是 high。记住下面这种图就 OK 了。
这幅图的含义是，如果二分查找的目标值 target 不在数组中，那么最后退出循环时，high 指向数组中刚好小于 target 的值，low 指向数组中刚好大于 target 的值。
三、第二种写法：两分支二分查找
while 循环条件是 low < high，退出循环时，一定有 low == high，不用纠结返回 low 还是返回 high。
循环里只写两个分支，一个分支排除中位数，另一个分支不排除中位数，不再单独对中位数做判断。
根据“排除中位数的逻辑”，会有以下两种情况：
if(排除中位数的逻辑) low = mid + 1;
else high = mid;
if(排除中位数的逻辑) high = mid - 1;
else low = mid;
因为有一个边界更新为中位数，为了避免死循环，所以有 取左中位数 和 取右中位数 的区别。
例如下面的代码就有陷入死循环的风险：
mid = (low + high) >>> 1; // 选择左中位数
if(排除中位数的逻辑) high = mid - 1;
else low = mid;
当候选区间只剩两个元素时，此时求得的左中位数就是左边界，一旦进入左边界更新为中位数的逻辑分支，下一次循环，左边界没有变，求得的左中位数还是左边界，左边界还是不变，就会陷入死循环。
解决办法是，对于左边界更新为中位数的情况，我们取右中位数。对于右边界更新为中位数的情况，我们取左中位数。
四、具体问题
4.1 找出升序数组中小于等于目标值的最大值
前面已经给出代码，不再重复列出。
4.2 找出升序数组中大于等于目标值的最小值
第一种写法：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid;
}
return low;
}
第二种写法（小于目标值的肯定不要，作为排除中位数的逻辑）：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
4.3 找出升序数组中小于目标值的最大值
第一种写法：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid - 1;
}
return high;
}
第二种写法（大于等于目标值的肯定不要，作为排除中位数的逻辑）：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high + 1) >>> 1;
if(a[mid] >= target) high = mid - 1;
else low = mid;
}
return low;
}
4.4 找出升序数组中大于目标值的最小值
第一种写法：
int binarySearch(int[] a, int target){
int low = 0, high = a.length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(a[mid] < target) low = mid + 1;
else if(a[mid] > target) high = mid - 1;
else return mid + 1;
}
return low;
}
第二种写法（小于等于目标值的肯定不要，作为排除中位数的逻辑）：
int binarySearch(int[] a, int target){
int low = 0, high = a.length;
while(low < high){
int mid = (low + high) >>> 1;
if(a[mid] <= target) low = mid + 1;
else high = mid;
}
return low;
}
五、最后
不是说第一种写法 while 循环条件一定要是 low <= high，只是 low <= high 更好。不是说第二种写法 while 循环条件一定要是 low < high，只是写 low < high 更好。
我还是推荐大家使用第一种写法，代码对称，写法固定，好记，只需要记住那张图就可以了。当然，第二种写法也不是白看的，当你看到别人用第二种写法时，能很快反应过来，他写的是什么，写的正不正确。
参考：leetcode 题解
