算法-二分搜索

发表于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

概述

二分搜索 用于有序数组查询操作，它可将操作时间复杂度降为 $O(log^N)$。

二分搜索思想十分简单：首先确定待搜索区间，随后获取区间中间值并将其与待搜索值进行比对，如果区间中间值大于待搜索值，则待搜索区间应为左半部分，反之待搜索区间应为右半部分，最后递归处理待搜索区间即可。

二分搜索实现比较困难，原因在于：若干边界条件需要判断。

实现

如上所言，二分搜索实现较为困难。我们在此引入两个简洁地二分搜索模板，第一个模板用于寻找最后一个 $\leq item$ 的元素位置下标，第二个模板用于寻找第一个 $\geq item$ 的元素位置下标。

模板一：

该模板根据中间值将区间划分为 $[l,mid]$ 和 $[mid + 1, r]$。

1
2
3
4
5
6
7
8
9
10
11
12
public int binarySearch(Integer[] objects, Integer item) {
    int l = 0, r = objects.length - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (objects[mid].compareTo(item) >= 0) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

模板二：

该模板根据中间值将区间划分为 $[l,mid - 1]$ 和 $[mid, r]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int binarySearch(Integer[] objects, Integer item) {
    int l = 0, r = objects.length - 1;
    while (l < r) {
        // 为防止死循环，需要如此取值。
        int mid = (l + r + 1) >> 1; 
        if (objects[mid].compareTo(item) <= 0) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

针对模板二中 mid 取值，做如下说明：

假定待搜索区间为 $[l,l+1]$ 且 $objects[l] \leq item$，此时如果采用 mid = (l + r) >> 1 ，则 mid = l，由于 $objects[mid] \leq item$，则更新后的待搜索区间仍为 $[l,l+1]$，此时即造成死循环；如果采用 mid = (l + r + 1) >> 1，则不会造成这种情况。