二分查找 : 那个隐藏了 10 年的 Java Bug

一个偶然的机会,我想起以前还在谷歌上班的时候,有时候大家会在饭桌上讨论最新想出来的一些面试题。在众多有趣又有难度的题目中,有一道老题却是大家都纷纷选择避开的,那就是去实现二分查找。

因为它很好写,却很难写对。可以想象问了这道题后,在5分钟之内面试的同学会相当自信的将那一小段代码交给我们,剩下的就是考验面试官能否在更短的时间内看出这段代码的bug了。

二分查找是什么呢,这个不只程序员,其他很多非技术人员也会。比如我想一个1到100以内的数,你来猜,我告诉你每次猜的是大了还是小了,你会先猜50,然后25, 然后。。。用不了几个问题就猜出来了。1到100范围太小的话,我们放大点猜个人名,你问中国人外国人,古代人现代人,男的女的,用不了几个问题也问出来了。在计算机里,则是在一个有序数组里面,不断通过二分的方法缩小关键字的可能下标范围。当然了,我们不一定在一个有序数组里查找,也可以在一个很大的状态空间里,去查找一个单调函数的取值。这样的做法,似乎编个程序很容易实现,但是,

D.Knuth大神说了:Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky 虽然二分查找的基本思想相对来说很直接,但具体实现起来有特别多的坑。

另一位大神,编程珠玑的作者Jon Bentley,他做了我们在文章开头不敢做的事,他布置作业让他的学生们写二分查找,然后他一个个来看。结果呢,他发现90%是错的。因此在他的编程珠玑这本书中,专门有一章讲解了二分查找,虽然他的范例仍然是错的,见下面的Java Bug。埋下这个bug的人,也正式Jon Bentley的学生。

还有好事者,更是找了许多教科书,发现20本教科书里面,只有5本是写对了的,于是他发了一篇文章到ACM。当然这是早在1988年的时候。

然而这些都不算啥,更能让人感觉幸灾乐祸的是,Java库里面的二分查找,有一个埋藏了10年之久的bug。这个bug呢,在 java.util.Arrays.binarySearch 里面,虽然这个bug的修复也已经是10年前的事了。那么我们来看下当年的错误代码吧。

大家可能很难看出来,那毕竟这个bug藏了10年,不太容易发现。问题就在于

int mid = (low + high) / 2;

这里。low + high 是会溢出的。只要这个数组我们开的足够大,比如1100000000,就能重现这个问题,虽然这需要我们费点内存。因此正确的解法是:int mid = (low + high) >>> 1; 三个>,无符号位移的意思。正如修复bug的同学说的那样:

"Can't even compute average of two ints" is pretty embarrassing.

这个bug的链接在这里。

那么我们究竟如何来把二分查找写正确呢?我们二分查找中常见的错误除了上面的溢出之外,最多的是下面几类:

  • 差1错误。我们的左端点应该是当前可能区间的最小范围,那么右端点是最大范围呢,还是最大范围+1呢。我们取了中间值之后,在缩小区间时,有没有保持左右端点的这个假设的一致性呢?
  • 死循环。我们做的是整数运算,整除2了之后,对于奇数和偶数的行为还不一样,很有可能有些情况下我们并没有减小取值范围,而形成死循环。
  • 退出条件。到底什么时候我们才觉得我们找不到呢?

我很喜欢二分查找这个案例。一个在理论上这么简单直接的算法,在计算机里实现却要考虑那么多实际的情况,除了理论的细化比如差1错误和退出条件,还有计算机的实际问题如整除2,死循环,以及上面提到的溢出。正如我们以前同事每天挂在嘴边的

You know the difference between in theory and in practice? In theory there’s no difference but in practice there are.

软件工程师,就是把现实生活用理论进行建模,然后再用现实来实现这样的理论。写出好的代码不容易,写出既让用户满意又好的代码,那更不容易。也许有时候,成就感就来自于此吧。



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部