二分法:擦肩而过的美好瞬间

二分法(BinarySearch),是一个简单却很容易写错的算法。据说,Jon Bentley(k-d tree的发明者)做过一次调查,90%的程序员,花上几个小时,也写不出一个正确的二分算法。我写了几个,发现成败在细节上。后来总结出了一个经验,就是把重点放在二分法那个擦肩而过的美好瞬间。下面通过几个例子来体会。

找寻插入位置

1
2
3
4
5
6
7
8
9
说,你有一个整数数组,已经排序完毕,升序,并且没有重复的元素。
问,给你一个整数,求它在数组中的插入位置。

拿[1, 4, 7, 8]来说,
0 -> 0,
2 -> 1,
5 -> 2,
7 -> 2,
9 -> 4

我写了如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(nums[mid] == target) {
return mid;
} else if(target > nums[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start;
}
}

确保相遇

当start比end小或相等的时候,我们都继续找,而当start超过end,他们擦肩而过的时候,我们停止循环。为了避免他们停滞不前,每次我们要么增加start,要么减小end,确保他们擦肩而过。

擦肩瞬间

由于每次要么start增加,要么end减小,只有一方会发生变化,必定有一个瞬间,他们相遇落在同一个位置上。这次相遇是最令人心动的地方,也是该算法,最需要注意的地方。请问在上述代码中,从while循环出来的时候,为什么返回的是start,而非end?请认真思考一下,再看我的分析。

让我们把注意力放在他们擦肩相遇的瞬间,start和end站在了同一个位置,start看一下目标值和眼下的值,如果发现目标大,start往前一步,超越了end,新的start必定是插入的正确位置;如果发现目标小,start让end走一步,start留在了原地,正好占用当下的插入位置,因为要插的值正好比当下的小。

是不是这个瞬间很美好?

求平方根

1
2
3
求整数的平方根,结果要整数。比如:
sqrt(16) = 4,
sqrt(15) = 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int mySqrt(int x) {
if(x == 0) return 0;
if(x == 1) return 1;
int start = 1;
int end = x / 2;
while(start <= end) {
int mid = start + (end - start) / 2;
int square = mid * mid;
if(square == x) return mid;
if(square > x || (square / mid != mid) ) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return end;
}
}

为什么出了while循环,我们返回的是end?擦肩而过的瞬间发生了什么?

求区间的头和尾

1
2
3
说,有一个整数数组,按升序排序完毕
求,目标值得首次和最后出现的位置,找不到返回[-1, -1]。时间复杂度必须控制在o(logn)
比如在[1, 2, 3, 3, 3, 4, 4]求3的区间,答案是[2, 4]
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
32
33
34
35
36
37
38
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{
searchLow(nums, target), searchHigh(nums, target)};
}

private int searchLow(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int mid = start + (end - start) /2;
if(target <= nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
if(start > nums.length - 1) return -1;
if(nums[end + 1] == target) return end + 1; //回头看
return -1;
}

private int searchHigh(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int mid = start + (end - start) /2;
if(target >= nums[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
if(end < 0) return -1;
if(nums[start - 1] == target) return start - 1;
return -1;
}
}

你能体会到擦肩而过的美妙吗?在找区间头的过程中,end在相遇的位置上看了一下目标值和眼下值,如果发现目标值小或正好,end就会往前走一步,翻过start。最后end回头看,那么相遇时的位置,要么区间头找到了,要么目标值不存在。

总结

二分法,是有规律可寻的,首先就是要确保start和end总有一方前进,进而确保擦肩而过跳出while循环。其次就是根据需求,决定在相遇的瞬间,是start还是end动。掌握了这个规律,你定能写出来正确的二分法。