乐者为王

Do one thing, and do it well.

我写的二分查找算法有bug!

看完 http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ 觉得很不服气,写个二分查找算法还不简单吗?分分钟搞定的事情。

按照它的要求,用Java写出以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int binarySearch(int[] array, int value) {
    int low = 0;
    int high = array.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (array[mid] < value) {
            low = mid + 1;
        } else if (array[mid] > value) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

把代码贴到评论区参加测试。

写代码和检查总共花费20分钟,75%的时间是用来在脑袋里模拟运算,防止数组索引溢出。然后编译2次,消除了两个语法错误(好久没写Java代码和使用Ruby的关系,竟然连个数组初始化都不会写了)。也想过数值溢出的问题,但是没想到点子上。结果恰恰倒在了这个地方。具体原因在 http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html 有描述。因为low + high的和会形成数值溢出,解决方法是采用:

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

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

Comments