没事系列.二分查找算法

二分查找的精髓在于，每查一次，待查找范围能缩小为原先的一半，由N变N/2，再变N/4，再变N/8…，直到只剩下一个元素。

写一个二分查找很容易，写一个好的二分查找很难。

EXAMPLE

下面是一个简单示例，要求查到某元素最先出现的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 最简单的思路，利用中间的数作为参考，找到了就往前(或往后)遍历。
public int getPosB(int[] A, int n, int val) {

    int min = 0, max = n - 1, middle;

    while (min <= max) {
        middle = (min + max) / 2;

        if (A[middle] == val) {
            // 向前遍历，找出第一次出现的那个数
            while (middle - 1 >= min && A[middle - 1] == val)
                middle--;
            return middle;
        }

        if (A[middle] > val) max = middle - 1;
        if (A[middle] < val) min = middle + 1;
    }

    return -1;
}

上面代码的缺点在于，利用二分查找找到目标值后，又使用了速度较慢的线性查找，我们可以将线性查找的内容也放入二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 给定一个整数数组A及它的大小n，同时给定要查找的元素val，请返回它在数组中的位置(从0开始)，
 * 若不存在该元素，返回-1。
 * 若该元素出现多次，请返回第一次出现的位置。
 * <p>
 * 稍微复杂的思路：将最小指针min与最大指针max都逼向最左边的元素，也就是第一次出现。
 */
private int getPos(int[] A, int n, int val) {
    int min = 0, max = n - 1, middle;

    while (min < max) {
        middle = min + (max - min) / 2; // 防止(min + max)溢出
        if (A[middle] == val)
            max = middle;
        else if (A[middle] > val)
            max = middle - 1;
        else if (A[middle] < val)
            min = middle + 1;
    }

    return A[min] == val ? min : -1;
}

改进后，中间指针middle不再作为最终结果的指针，最终指针由min担当，将min和max都逼向最终值（而不是将middle逼向最终值），当min == max时就能结束循环。