折半查找 · Yukki 的个人站

基本原理

什么是折半查找

折半查找（Binary Search），也叫二分查找。其核心思想是：

每次将当前查找区间缩小为原来的一半。

假设有序表为：

10,\ 20,\ 30,\ 40,\ 50,\ 60,\ 70

查找 60 时，先与中间元素 40 比较。因为 $60>40$ ，所以可以直接舍弃前一半 $10,20,30$ ，只在 $50,60,70$ 中继续查找。

因此，折半查找的本质是：

不断排除一半不可能的元素。

适用条件

折半查找要求查找表：

必须有序；
必须能够随机访问。

所以它适用于有序的顺序表，例如数组或其他顺序存储结构，而不适合普通链表。

链表并非不能排序，而是访问中间元素时需要从头遍历，无法像数组一样直接定位，因而失去了折半查找的效率优势。

查找过程

设当前查找区间为 $[low, high]$ ，中间位置为 $mid$ 。将目标关键字 $key$ 与中间元素 $Q[mid]$ 比较：

若 $key=Q[mid]$ ，查找成功；
若 $key<Q[mid]$ ，继续查找左半部分；
若 $key>Q[mid]$ ，继续查找右半部分。

不断重复，直到找到目标或查找区间为空。

复杂度分析

时间复杂度

假设开始有 $n$ 个元素，每次比较后，剩余查找范围依次约为：

\frac{n}{2},\ \frac{n}{4},\ \frac{n}{8},\ \ldots,\ \frac{n}{2^k}

当只剩约一个元素时，有：

\frac{n}{2^k}\approx1 \quad\Rightarrow\quad 2^k\approx n \quad\Rightarrow\quad k\approx\log_2 n

因此，折半查找的时间复杂度为：

\boxed{O(\log n)}

最好与最坏情况

最好情况：第一次比较时，中间元素就是目标，时间复杂度为 $O(1)$ 。
最坏情况：不断折半，直到最后才找到目标，或最终确认目标不存在。比较次数约为 $\lfloor\log_2 n\rfloor+1$ ，时间复杂度为 $O(\log n)$ 。

折半查找判定树

折半查找的过程可以表示为一棵折半查找判定树。

例如，对有序表 $1,2,3,4,5,6,7$ 进行折半查找，第一次检查中间元素 4，所以 4 是根结点：

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

查找 4：比较 1 次；
查找 2 或 6：比较 2 次；
查找 1、3、5 或 7：比较 3 次。

重点：元素在判定树中的层数，就是成功查找到该元素所需的比较次数。

平均查找长度（ASL）

ASL（Average Search Length，平均查找长度）表示查找一个元素平均需要比较多少次。

成功查找时：

ASL_{\text{成功}} = \frac{\sum(\text{每个元素的比较次数})}{n}

如果每个元素被查找的概率相同，ASL 就是判定树中所有结点层数的平均值。以上面的 7 个元素为例：

ASL = \frac{1\times1+2\times2+4\times3}{7} = \frac{17}{7}

计算时需要牢记：

比较次数 = 判定树层数。

优缺点与适用场景

折半查找的优点是查找效率高，时间复杂度为 $O(\log n)$ ，相比时间复杂度为 $O(n)$ 的顺序查找，在数据量较大时优势明显。

它的局限主要有两点：

数据必须有序；
最好采用顺序存储结构。

如果数据需要频繁插入、删除，为了保持数组有序，移动元素的代价可能达到 $O(n)$ 。因此，折半查找特别适合：

数据变化不频繁，但查询非常频繁的静态查找表。

C++ 实现

下面的函数查找成功时返回元素从 1 开始计数的位置，失败时返回 -1：

int Binary_Search(const std::vector<int>& Q, int x) {
    int left = 0;
    int right = static_cast<int>(Q.size()) - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (Q[mid] == x) {
            return mid + 1;
        } else if (Q[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

今天有点不太想学，或者说今天学的比较快。
反正时间比较短我就累了。
下了一天的雨，别下了。
我还要去学校。

中岛由贵