Joshua Bloch, 获得过Jolt最畅销奖的《Effective Java》的作者, 是Sun Microsystems的杰出工程师和Transarc的资深系统设计师, J2SE 5.0 Tiger的代言人和领路人, 也是还是JSR166的发起人之一..
后来, Joshua Bloch去了Google, 成为了
Google的首席工程师Joshua Bloch拥有卡耐基.梅隆大学(CMU)计算机科学的博士学位。
在
最近Joshua Bloch的一篇文章里, Joshua Bloch回忆了当年在CMU上课的时候, vividly Jon Bentley
第一节算法课, 就要求所有刚进来的PHD学生, 每人都写一个二分查找算法. 然后发现, 多数人的算法都存在BUG, 这在当时给了Joshua
Bloch 一个很深的印象..
在之后, Joshua Bloch 负责java.util.Arrays 代码编写的时候, 采用了Bentley 在<<Programming Pearls >>一书中的二分查找算法, 结果在8年后的今天,
Joshua Bloch 发现, 这里面原来还是有一个BUG.
问题到底是出在哪里? 竟然逃过了Bentley 和Joshua Bloch 的双重检测?
一起来看看java.util.Arrays的代码:
1: public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal < key)
10: low = mid + 1;
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }
这是很经典的一个二分查找算法.
bug出现在第6行:
6: int mid =(low + high) / 2;
在一般情况下, 这个语句是不会出错的, 但是, 当low+high的值超过了最大的正int值 (231 - 1) 的时候, mid会变成负值, 这个时候, 会抛出ArrayIndexOutOfBoundsException 异常..所以当一个数组包含超过2的30次方 个元素的时候, 就很可能会带来问题... 当然, 在一般的应用里面, 很少数组会包含那么多元素, 但是现在这样的情况已经越来越多了, 比如Google的海量运算..
那如何解决这个问题?
很简单, 修改这行语句为:
6: int mid = low + ((high - low) / 2);
或者
6: int mid = (low + high) >>> 1;
在c或者c++中, 则可以如下实现:
6: mid = ((unsigned) (low + high)) >> 1;
这个问题告诉我们, 无论什么时候, 我们都不要想当然我们的程序是完美的. 我们需要细心的设计,测试再测试,符合规范的方法等等...对此, 你有什么经验和大家分享吗?
同样给我们带来的思考是: 8年了, java.util.Arrays 竟然存在这样一个bug, 这不得不让我们对JDK本身的测试性, 稳定性 怀有疑问.. 将来又会有多少个类似的bug出现呢?