《数据结构与算法》——二分查找法

二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。后续的课程中还会学习更多的查找算法，但在此之前，不妨用它作为入门。

1) 基础版

需求：在有序数组 A 内，查找值 target

• 如果找到返回索引

• 如果找不到返回 -1

算法描述

P.S.

• 对于一个算法来讲，都有较为严谨的描述，上面是一个例子

• 后续讲解时，以简明直白为目标，不会总以上面的方式来描述算法

java实现

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) / 2;
        if (target < a[m]) {            // 在左边
            j = m - 1;
        } else if (a[m] < target) {     // 在右边
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

java 实现（基础优化版）

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {            // 在左边
            j = m - 1;
        } else if (a[m] < target) {     // 在右边
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

• $i,j$ 对应着搜索区间 $[0,a.length-1]$（注意是闭合的区间），$i<=j$ 意味着搜索区间内还有未比较的元素，$i,j$ 指向的元素也可能是比较的目标

  • 思考：如果不加 $i==j$ 行不行？

  • 回答：不行，因为这意味着 $i,j$ 指向的元素会漏过比较

• $m$ 对应着中间位置，中间位置左边和右边的元素可能不相等（差一个），不会影响结果

• 如果某次未找到，那么缩小后的区间内不包含 $m$

2) 改变版

另一种写法

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length;
    while (i < j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {            // 在左边
            j = m;
        } else if (a[m] < target) {     // 在右边
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

• i,j 对应着搜索区间 [0,a.length)（注意是左闭右开的区间），i<j 意味着搜索区间内还有未比较的元素，j 指向的一定不是查找目标

  • 思考：为啥这次不加 i==j 的条件了？

  • 回答：这回 $j$ 指向的不是查找目标，如果还加 $i==j$ 条件，就意味着 $j$ 指向的还会再次比较，找不到时，会死循环

• 如果某次要缩小右边界，那么 $j=m$，因为此时的 m 已经不是查找目标了