单调数组上的二分查找算法

二分查找算法 是一种在 有序数组 中查找给定元素的搜索算法。

算法过程 ¶

二分查找的过程如下图所示：

具体的查找过程：

• 步骤 1 ：初始化查找范围为整个有序数组，即低位 $low$ 为 $0$ , 高位 $high$ 为数组的大小 $n$ 。
• 步骤 2 ：比较中间位置 $mid = (low + high) / 2$ 的元素和目标元素的大小关系：

  • 如果目标元素较小，则降低高位，即 $high = mid - 1$ 。

    这缩小了一半的查找范围，重复查找，回到步骤 2 。

  • 如果目标元素较大，则增大低位，即 $low = mid + 1$ 。

    这缩小了一半的查找范围，重复查找，回到步骤 2 。

  • 如果正好相等，查找完成，结束整个查找。

• 步骤 3 ：直到查找范围无法继续缩小下去，即当 $low <= high$ 不再成立时，未查找到。

具体的算法过程如下图所示，图中的红色框是每次的查找范围，由 $low$ 开始，到 $high$ 结束。 每次查找范围都会缩减一半。

复杂度分析 ¶

假设总共需要迭代 $k$ 次才可以找到目标。

因为每次查找，范围即缩小为原来的一半，最终要缩小为 $1$ 才可以，即 $n * (1/2) ^ k = 1$ ， 得到 $ k = \log {n}$ 。 即二分查找的时间复杂度是 $\log{n}$ 。

非递归实现的空间复杂度是 $O(1)$ 。

C 语言实现 ¶

// 从大小为 n 的数组 a 中查找元素 target.
// 返回 target 的位置；如果找不到，返回 -1.
int BinarySearch(int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    int mid = 0;

    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] < target) {
            low = mid + 1;
        } else if (a[mid] > target) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1; // 未找到
}

数学上的二分法 ¶

二分法在数学上可以用来求 单调函数 的近似根，和计算机算法中的二分法类似：

1. 先找出跨零值的区间 $[a, b]$ ，使得 $f(a)$ 和 $f(b)$ 异号，则这个区间内必然包含函数的根。
2. 求该函数的中点 $m = \frac {a+b} {2}$ 。
3. 如果 $f(m)$ 和 $f(a)$ 正负号相同，则取 $[m, b]$ 为新的区间，反之则取 $[a, m]$ 。
4. 重复第 2、3 两步，直到理想精度为止，即 $(\frac {f(b) - f(a)} {2} < e$ 时终止（ $e$ 是理想误差） 。

延伸：

• 二分法的二段性、两套模板 和 答案判定
• 黄金分割法 (三分法)

（完）

本文原始链接地址： https://hit9.dev/post/algorithm-binary-search