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

发表于

二分法(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动。掌握了这个规律，你定能写出来正确的二分法。