二分查找的那些坑

听说很多人写不对二分查找，如果不好好总结一下，我大概也会是其中之一。。

历史上二分查找的bug

二分查找虽然原理很简单，实现起来却有很多的坑。
Algorithms - Coursera
《编程珠玑》的作者做实验发现90%的人写不对二分查找，然后亲手在该书里写下一个带 bug 的 binary search... 据说该 bug 在书里呆了二十年没人发现，而这本书还是一本人人交手称赞的好书。
然后 java 标准库里，一个和《编程珠玑》同样的 bug 在 2006 年才被发现。。
那这个 bug 是啥呢？是一个很好理解的问题：整数溢出

public static int binarySearch(int[] nums, int target, int lo, int hi){
    while(lo <= hi){
        int mid = lo + (hi - lo) / 2;
        // int mid = (lo + hi) / 2;         // the bug one
        if(nums[mid] == target) return mid;
        
        if(nums[mid] > target) hi = mid - 1;
        else                lo = mid + 1;
    }

    return -1;
}

要写好这东西，关键是两点，一个是边界的缩减，一个是那句可能会导致溢出的语句。
顺手再上leetcode刷两道二分查找题，巩固一下。。

二分查找的那些坑

历史上二分查找的bug

参考