如何正确的写出二分查找

还记得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算法设计巧妙的地方,整体代码简洁、优雅。看完之后让人感觉豁然开朗、收获颇丰!