How Hard Is It to Write a Correct Program?

题图：Bleaching Ground at Scheveningen | Vincent van Gogh

玩过“猜数字”的游戏吧？我在心里想一个1到100的数字，让你来猜，每次你说出所猜的数，我会告诉你比我想的是大了还是小了，直到猜中为止。你会怎么猜？第一次你应该会猜50，如果我说大了，你第二次应该会猜25……用这样的方法最多猜8次就能猜中。

这其实就是二分查找的算法。

也许你认为，这么一个简单的算法，用编程来正确实现，应该不难吧？但是，我可以负责任地告诉你，比你想象的难得多。高纳德Knuth在《计算机编程的艺术》第三卷“排序和搜索”的6.2.1节中说，第一篇二分搜索论文在1946年就发表了（话说那时候能用来编程的计算机才刚出现吧），第一个没有错误的二分搜索程序却直到1962年才出现。

在第一篇二分搜索论文发表之后40年的1986年，Jon Bentley（他在家里和办公室的案头各放了一套Knuth的《计算机编程的艺术》）在《编程珠玑》中写道：“提供充足的时间，竟然仅有10%的专业程序员能够将（二分搜索算法）这个小程序编写正确。”这是Jon Bentley在卡内基梅隆大学开设的算法课上博士生们的真实表现。Jon Bentley在课上详细讲述了二分搜索算法在实现中容易犯的错误和正确的实现方法。后来，这些内容成为《编程珠玑》这本经典著作中的第四章。

当年这些学生中，有一位对这一课印象深刻。这个学生名叫Joshua Bloch。用Java的人都用过JDK的容器类List,Set, Map等等，这些代码每天在全世界成千上万的JVM里面运行，数以万计的码农在自己的代码中使用这些类。这些经典的库代码是谁写的？正是Joshua Bloch。现在他是Google的首席Java架构师。

大约在Jon Bentley讲那堂课的12年之后，那篇论文发表的32年之后，1998年，Joshua Bloch开始编码实现JDK1.2的容器类，采用了老师Jon Bentley 所讲和所写的二分搜索算法的实现方法。

又8年之后的2006年，JDK 6即将发布的时候，Joshua Bloch 发现，原来这个实现代码里面还是有一个BUG！

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

就是这一句有问题，有可能导致整数溢出。如当low=0x7FFFFFFFE，high=0x1000，在JDK 5中mid=0xC00007FF，这是个负数，此时该方法就会抛出ArrayIndexOutOfBoundsException数组越界的异常。

抛异常还不算严重。整数溢出的问题在严重的情况下会成为一个被利用的安全问题。Phrack杂志第60期第9篇，《Big Loop Integer Protection》中详细分析了整数溢出的问题。Xorg X Server曾爆出多个整数溢出漏洞（CVE-2014-8093），可能导致任意代码执行。

就是说，高纳德Knuth所说的一直没有正确实现的二分搜索算法，实际上是从1946到2006年，一共60年，都没有正确的实现！

码农的工作有多难，这下知道了吧？

所以，如果你的有一位恰好是一个码农的朋友，请你爱他/她多一些，多一些，多一些。重要的事情说三遍，能让你长按并识别下面的二维码吗？