如何正确的写出二分查找

算法

还记得Jon Bentley关于二分查找的那句著名言论吗？————90%以上的程序员无法正确无误的写出二分查找代码！几年前刚毕业的时候无意间看到这句话的时候，还有点不以为然，感觉就是一个普通的分治法的算法嘛，有这么夸张？
今天在看SparseArray源码的时候，碰巧发现一个设计的很巧妙的二分查找算法。先看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static int binarySearch(int[] array, int size, int value) {
    int lo = 0;
    int hi = size - 1;
    while (lo <= hi) {
        final int mid = (lo + hi) >>> 1;
        final int midVal = array[mid];
        if (midVal < value) {
            lo = mid + 1;
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            return mid;  // value found
        }
    }
    return ~lo;  // value not present
}

和最常用的采用尾递归实现二分查找的方式不同，改成了循环。第5行寻找中间位置的时候采用高低位相加然后无符号右移1位，这里就比较与众不同了。对于一般的程序员来说，最普遍的写法就是:

1
(lo + hi) / 2

或者

1
(lo + hi) >> 1

但是这么写有一个问题，考虑某些极端情况，比如lo和hi都比较大，它们的和超出了int的最大值2147483647，那么此时的运算结果就会溢出，从而产生负数，mid位置的计算就有问题，所以大多数二分查找算法在实现时为了避免溢出，求mid的算法一般都会这么写：

1
lo + (hi -lo) >> 1

减法可以使得结果为一个hi还小的值，至于移位运算和直接的除法运算，移位要更快一点。
其实仔细想一下，既然(lo + hi) >> 1 右移1位有可能会溢出产生负数，那么 >>> 无符号的右移不就可以避免这个问题了吗？所以Google的做法是：

1
(lo + hi) >>> 1

是不是感觉大学期间学的那些计算机基础知识还是有很用啊？
找到中间mid的位置之后，后面的逻辑没什么好说了，典型的分治法。关键看一下第15行的返回值

1
return ~lo;

程序执行到这里，说明从有序数组中没有找到我们想要查找的数值，其实lo就是这个数要在该有序数组中插入的位置，返回~lo变为负数，主要用途在put方法中，看一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Adds a mapping from the specified key to the specified value,
 * replacing the previous mapping from the specified key if there
 * was one.
 */
public void put(int key, E value) {
    int i = binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        if (mGarbage && mSize >= mKeys.length) {
            gc();
            // Search again because indices may have changed.
            i = ~binarySearch(mKeys, mSize, key);
        }
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

在第9行，如果二分查找算法binarySearch返回的值i >= 0 ，说明找到了，那么直接更新该下标处的值，else说明数组中没有要查找的值，返回了要插入位置的 ～ 位运算符的值，那么此时我们再 ~i 一下，不就拿到要插入的位置了吗？后面就是mKeys和mValues数组的部分移位操作。

到此，可以看到binarySearch算法设计巧妙的地方，整体代码简洁、优雅。看完之后让人感觉豁然开朗、收获颇丰！