欢迎访问昆山宝鼎软件有限公司网站! 设为首页 | 网站地图 | XML | RSS订阅 | 宝鼎邮箱 | 后台管理


新闻资讯

MENU

软件开发知识

二分查找 : 谁人埋 图纸加密 没了 10 年的 Java Bug

点击: 次  来源:宝鼎软件 时间:2017-09-02

原文出处: ccmouse

一个偶尔的时机,我想起以前还在谷歌上班的时候,有时候各人会在饭桌上接头最新想出来的一些口试题。在浩瀚有趣又有难度的题目中,有一道老题却是各人都纷纷选择避开的,那就是去实现二分查找。

因为它很好写,却很难写对。可以想象问了这道题后,在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年前的事了。那么我们来看下当年的错误代码吧。

二分查找 : 那个埋 图纸加密 没了 10 年的 Java Bug

各人大概很丢脸出来,那究竟这个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.

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