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

因为它很好写，却很难写对。可以想象问了这道题后，在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错误和退出条件，尚有计较机的实际问题如整除2，死轮回，以及上面提到的溢出。正如我们以前同事天天挂在嘴边的

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

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