细说二分查找

发表于 更新于 阅读次数：

细说以下二分查找中的那些坑。

二分查找是一个听起来很简单的算法，但是实际上这个算法有很多坑，想快速写出百分百正确的二分查找并不容易。

Donald Knuth 在其著作 The Art of Computer Programming, Volume 3: Sorting and Searching 中提到，“虽然第一篇二分搜索的论文在1946年就发表了，但是第一个没有错误的二分搜索程序却直到1962年才出现。”

然而，实际上，1962年出现的一些二分搜索算法，现在看来依然有bug，请往下看。

曾经的 Java 类库中的 bug

当年 Java 类库中的二分搜索算法也有 bug，当时的算法没有考虑整形相加可能的溢出问题。当时的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];

        if (midVal < key) {
            low = mid + 1;
        } else if (midVal > key) {
            high = mid - 1;
        } else {
            return mid; // key found
        }
        return -(low + 1); // key notfound
    }
}

其中，low + high 是有可能溢出的，如果要解决这个问题，可以把计算 mid 的这句改为：

1
int mid = (low + high) >>> 1

之所以可以改为这样，并不是因为对所有的数字计算平均值都可以采用这种方法，只是这种写法在二分搜索这个算法中是正确的。

>>> 移位运算符会把符号位一起移动。int 类型的值是区分正负的，一个 int 型变量的二进制形式的首位为 0，代表这个数是正数，为1代表这个数是负数。如果两个数相加发生了溢出，那么就相当于符号位后边的各位相加之后向符号位发生了进位，两个正数相加，但是符号为却变成了1，结果变成了一个负数，这就是出错的情况。但是如果我们使用 >>> 运算符，相当于不考虑符号位的存在了，把二进制的第一位也当成正常存储值的位，这样两个数相加，直接右移一位，原本会溢出的结果，会得到正确的答案。

但是如果有两个负数，两数相加之后有可能会溢出下限，使用 >>> 运算符并不行。

之所以在二分算法中可以这么做，是因为我们是对数组的下标进行计算，而下标只能是正数，不能是负数。

当年写出这个 Bug 的作者 Joshua Bloch 亲自写文章讲这件事：Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken - Joshua Bloch

STL 中的 lower_bound 和 upper_bound

两个函数其实都是求“下界”。

lower_bound() 是求区间内第一个大于等于某个值的元素的索引。

upper_bound() 是求区间内第一个大于某个值的元素的索引。

两个函数的实现极其相似，lower_bound() 中的判断部分是 comp(*it, value)，而 upper_bound() 中是 !comp(*it, value)。相当于第一个是 if(array[mid] < value)，第二个是 if(!(array[mid] > value))。

参考：

std::lower_bound - cppreference.com

std::upper_bound - cppreference.com

参考资料

  1. 强烈推荐：二分查找有几种写法？它们的区别是什么？ - 知乎
  2. 用Java实现C++::std中的upper_bound和lower_bound
  3. 二分查找–那个隐藏了10年的Java Bug
  4. 位运算相关 - 52Heartz’s Blog
  5. 计算两个数的平均数 - 52Heartz’s Blog
  6. 编程珠玑. 第2版. 2008.10. 人民邮电出版社. 第4章. 编写正确的程序.
  7. 【二分查找法】你真的写对了吗？
  8. Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken - Joshua Bloch
  9. 拓展：【编程珠玑】第二章 二分查找的巧妙应用