如果不能正常显示,请查看原文 , 或返回

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

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

ccmouse 慕课网imooc订阅号
慕课网imooc订阅号

imooc--com

慕课网官方的订阅号,每天推送来着一线IT大咖的技术干货、职场经验,更重要是周周有大家最喜爱的慕粉福利活动!

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


因为它很好写,却很难写对。可以想象问了这道题后,在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的链接在这里:http://bugs.java.com/bugdatabase/view_bug.do?bug_id=5045582


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

1.差1错误。我们的左端点应该是当前可能区间的最小范围,那么右端点是最大范围呢,还是最大范围+1呢。我们取了中间值之后,在缩小区间时,有没有保持左右端点的这个假设的一致性呢?


2.死循环。我们做的是整数运算,整除2了之后,对于奇数和偶数的行为还不一样,很有可能有些情况下我们并没有减小取值范围,而形成死循环。


3.退出条件。到底什么时候我们才觉得我们找不到呢?


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

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




作者ccmouse,是高级软件工程师和原Google“校招”命题组成员

曾就职于谷歌和摩根士丹利,担任高级软件工程师,Tech Leader,拥有十余年后端开发经验,精通C++,Java,分布式系统开发,曾参与过金融、搜索及在线广告系统等多个不同领域的开发工作。拥有多年的面试官经历,曾参与Google、摩根士丹利“校招”出题工作。


这次在慕课网推出《Google面试官亲授 校招面试》,结合当下秋招的热度,让你先人一步拿到offer。


点击下方
阅读原文
,抢先体验教程详情


ccmouse

赞赏

长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

返回