今天想来说说二分查找，因为最近笔者的同学在面试时正好遇到了，而自己以前还真没认真研究过。
说起二分查找，对算法和数据结构比较熟悉的都知道这是一个复杂度为 O(logN) 的典型分治算法，它的用途是在有序数组中查找某个数是否存在。但就是这么听起来很普通的算法却常常很难完全写对。
- 据D.Knuth在《计算机程序设计的艺术 第3卷：排序和查找》书中指出，虽然二分查找1946年就公诸于世，但1962年才有人写出没有 bug 的二分查找程序。
- 除此之外，就连我们熟悉的 Java 语言里 JDK 的二分查找
java.util.Arrays.binarySearch中也曾有一个隐藏了10年之久bug!（文末附bug链接）不过，这个bug已经不是什么新鲜事了，是 JDK5 时代的产物了，不过我们可以再来回顾一下，看看我们平常是不是就在写bug，是不是真应了那个表情包“哟，写bug呢”🙊
// 这段代码有毒，请勿模仿
public static int binarySearch(int[] a, int key){
int low = 0;
int high = a.length - 1;
while(low <= high){
int mid = (low + high) >> 1;
int midVal = a[mid];
if(midVal < key)
low = mid + 1;
else if(midVal > key)
high = mid -1;
else
return mid;
}
return - (low + 1);
}
乍一看这段代码似乎也没什么问题，但其中的几处细节是需要注意的，而这几处细节恰巧也是面试中经常遇见的（笔者的同学最近面试某大厂就被问到了）。
实际上，上述代码的问题就出在int mid = (low + high) >> 1，这句可能导致整数溢出，此时该方法就会抛出数组越界的异常，这个bug直接导致了 JDK6 之前的 binarySearch 无法正确处理大数组的情况。这个bug直到 JDK6 才得到修复。修复后代码是int mid = (low + high) >>> 1，将带符号右移修复成无符号右移，目前 JDK8里面的 binarySearch 就是这样。当然，除了这种方法之外，我们还可以这样写int mid = low + ((high - low) >> 1)。回想一下，你是不是也曾写过类似bug呢？
当然，今天学习时除了看到这个比较明显的细节外，还看到有两个地方也需要注意：
- 判断循环体是否终止的语句的编写
- 边界值 low, high 和区间值这三个地方要保持一致
对于第2点，具体一点就是，如果令 high = n - 1 (n是数组长度)，则 while 的循环条件为 low <= high，从而更新右边界位置的时候为 high = mid - 1；而如果令 high = n，则 while 循环的循环条件为 left < right，从而更新右边界位置的时候为 high = mid。同时，mid 的计算不能写在循环外，否则无法得到更新。
下面是一份无递归版本的参考代码：
public static int binarySearch(int[] a, int n, int key){
int left = 0;
int right = n - 1;
while (left <= right){
int mid = left + ((right - left) >> 1);
if (a[mid] > key)
right = mid - 1;
else if(a[mid] < key)
left = mid + 1;
else
return mid;
}
return -1;
}
当然，上述代码并没有判断输入异常之类的，还有递归版本等等，大家可以看看文末提供的二分搜索算法维基百科上面的例子。
总结一下，二分查找大的方面需要注意三点：
- mid 赋值问题，注意溢出情况。
- 判断 while 循环体是否终止的语句的编写
- 边界值 left, right 和区间值这三个地方要保持一致
参考：
