【原创】java.util.Arrays的改进

在JDK1.5或之前版本的JDK中，类java.util.Arrays中有二分查找法binarySearch(type[],int key)，如：

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

	while (low <= high) {
	    int mid = (low + high) >> 1;
	    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.
    }

有一个隐患：

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

一般情况下是不会有问题的(因为不会有这么长的Array)，但可能在64位的机器上，当low + high超出整数的最大值的时候会出现难以预料的错误结果或死循环，但不报错。

以上代码的作者是Joshua Bloch，他是《Effective Java》的作者, 也是Sun的杰出工程师。Josh Bloch 早就在博客中发表文章就为JDK中存在了这么久的Bug感到焦虑。
还好在JDK1.6中有了改进，但我觉得不是最好的解决方案。

在JDK1.6中改成了如下：

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

这样的话，当low + high超出整数的最大值的时候会抛出ArrayIndexOutOfBoundsException异常，因为mid是负数。

但我觉得这样并不是最好的解决办法，我很奇怪为什么不修改成下面的，就可以输出正确结果

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

评论

1 楼 pgty 2008-10-03  

改成这样就可以了 int mid = low + ((high - low)>>>1);