几乎所有的binary search都是错的

这个是来自Joshua Bloch的一篇文章:几乎所有的折半查找/合并排序都是有问题的,请注意:是几乎所有的,你自己写的,以JDK为例的各种库的,几乎都是错的

早年Joshua(Java主要作者之一,effective java的作者)在CMU念博士的时候,Jon Bentley(编程珠玑作者)给他上算法课,第一讲Jon让Joshua这些博士生现场写个binary search,然后指出几乎所有的人写的都是错的。后来这个内容成为了编程珠玑的第五章. 读完之后的感受是:‘写一段,哪怕是一小段完全没bug的程序好难’,当然Jon在书里给出了binary search的正确写法(c语言)

转眼到了2006年,当年的学生Joshua发现老师给出的代码里面还有个bug。这个bug不仅在书中过了20年无人发现,还在JDK里安稳的呆了9年,直到它搞崩了某人的程序,才被作为一个bug报上来:

下边这段代码是Joshua写在java.util.Arrays里面的,看看你能不能发现bug(肯定不能啊。。。)

public static int binarySearch(int[] a, int key) {
  int low = 0;
int high = a.length - 1;

while (low <= high) {
    int mid = (low + high) / 2;
    int midVal = a[mid];

    if (midVal < key)
         low = mid + 1
     else if (midVal > key)
         high = mid - 1;
     else
         return mid; // key found
 }
 return -(low + 1);  // key not found.
}

bug在这行:

     int mid =(low + high) / 2;

当low和high相加足够大,大于(2^31 – 1)的时候. 会溢出得到一个负数. 在C语言里,数组不会做边界检查,所以会有个不确定的行为。 Java会跑出ArrayIndexOutOfBoundsException.

一个简单的fix:

   int mid = low + ((high - low) / 2);

这个更快, 当然如果你熟悉>>>的话,也一样清晰(>>> 是逻辑右移, >> 是算术右移,保留正负数符号):

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

C和C++没有>>>操作符, 可以先转化为unsigned int,用>>来做:

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

修改后的binary search应该是正确的了吧?一个正确的函数得经过所有可能的验证才行,我们通过了所有可能的验证了吗?

这个问题同样存在于mergesort,或者说所有的分而治之算法都可能有这个潜在问题. 从这个bug中,我们应该学会谦逊:写一段没bug的代码是何等的艰难,而我们的世界运行在复杂、庞大的代码之上.

作为程序员的我们,即便使用所有可能的方法来避免bug:好好设计、认真测试、做静态检查、组织代码review. 即使如此,我们也不得不面对这样一个事实:bug与我们同在,bug会潜伏在系统长达半世纪,无视于我们最大程度的努力. 所以:认真的对待每一行代码,始终保持警惕.

发表评论

电子邮件地址不会被公开。 必填项已用*标注