折半查找 · 融合风（象牙 + Obsidian 入口）

速查 ▾

项目	值
主题	折半查找（二分查找）
核心概念	在有序顺序表上，每次与中间元素比较，范围减半
时间复杂度	$O(\log_2 n)$
难度	⭐⭐
重要性	⭐⭐

核心概念 ▾

折半查找（又称二分查找）是一种在有序顺序表上进行查找的高效算法。其核心思想是：

将待查关键字与有序表的中间位置元素进行比较，若相等则查找成功；若关键字小于中间元素，则在左半部分继续查找；若大于，则在右半部分继续查找。每次将查找范围缩小一半。

前提条件

存储结构必须是顺序表（数组）：不适用于链表（因为需要随机访问中间元素）
数据必须有序：通常是递增有序

判定树

折半查找的比较过程可以用一棵二叉树来描述，称为折半查找判定树：

每个结点表示一次比较，结点值为该位置的关键字
左子树：比当前关键字小的部分
右子树：比当前关键字大的部分
判定树是平衡二叉树（但不一定是满二叉树或完全二叉树）

判定树的构造规律

对于有序数组 a[low..high]：

根结点 $= mid = \lfloor(low + high) / 2\rfloor$（向下取整）
左子树 $= a[low..mid-1]$ 的判定树
右子树 $= a[mid+1..high]$ 的判定树

408 注意mid 的取法通常为 $\lfloor(low+high)/2\rfloor$（向下取整），不同教材可能用向上取整，会导致判定树形态不同，但不影响查找长度的计算。

算法步骤 ▾

标准流程

在有序数组 a[0..n-1] 中查找关键字 key：
1. low = 0, high = n - 1
2. 当 low <= high 时，重复：
   2.1 mid = (low + high) / 2（向下取整）
   2.2 若 key == a[mid]，查找成功，返回 mid
   2.3 若 key < a[mid]，high = mid - 1（在左半部分查找）
   2.4 若 key > a[mid]，low = mid + 1（在右半部分查找）
3. 若 low > high，查找失败

查找路径

查找过程中访问的 mid 序列称为查找路径。查找成功的路径长度 = 比较次数。查找失败的路径是从根到某个外部结点（空指针）的路径。

平均查找长度（ASL）

查找成功的 ASL：

$$ASL_{成功} = \frac{1}{n} \sum_{i=1}^{n} C_i$$

其中 $C_i$ 是查找第 i 个元素所需的比较次数（即该结点在判定树中的层数）。

查找失败的 ASL：

$$ASL_{失败} = \frac{1}{n+1} \sum_{j=0}^{n} C_j'$$

其中 $C_j'$ 是查找失败时到达判定树外部结点的比较次数。判定树有 n+1 个失败结点（n 个元素之间和两端的"空隙"）。

代码实现（C 语言） ▾

递归版

// 在有序数组 a[low..high] 中查找 key
int BinSearch_Recursive(int a[], int low, int high, int key) {
    if (low > high) return -1;         // 查找失败
    int mid = (low + high) / 2;        // 向下取整
    if (key == a[mid])
        return mid;                     // 查找成功
    else if (key < a[mid])
        return BinSearch_Recursive(a, low, mid - 1, key);  // 左半部分
    else
        return BinSearch_Recursive(a, mid + 1, high, key); // 右半部分
}

非递归版

// 在有序数组 a[0..n-1] 中查找 key
int BinSearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == a[mid])
            return mid;                 // 查找成功
        else if (key < a[mid])
            high = mid - 1;             // 左半部分
        else
            low = mid + 1;             // 右半部分
    }
    return -1;                          // 查找失败
}

查找第一个 $\geq key$ 的位置（lower_bound）

// 返回第一个 >= key 的元素下标（若不存在返回 n）
int LowerBound(int a[], int n, int key) {
    int low = 0, high = n, mid;        // 注意 high = n，不是 n-1
    while (low < high) {               // 注意是 <，不是 <=
        mid = (low + high) / 2;
        if (a[mid] >= key)
            high = mid;                // 不是 mid - 1
        else
            low = mid + 1;
    }
    return low;
}

查找第一个 $> key$ 的位置（upper_bound）

int UpperBound(int a[], int n, int key) {
    int low = 0, high = n, mid;
    while (low < high) {
        mid = (low + high) / 2;
        if (a[mid] > key)
            high = mid;
        else
            low = mid + 1;             // a[mid] == key 时也往右
    }
    return low;
}

手算示例 ▾

例题 1：折半查找过程

有序数组 a[] = {7, 14, 18, 21, 25, 29, 31, 35, 38, 42}，查找 key = 18

第 1 次比较：low=0, high=9, mid=4
  a[4]=25, key=18 < 25 → high=3

第 2 次比较：low=0, high=3, mid=1
  a[1]=14, key=18 > 14 → low=2

第 3 次比较：low=2, high=3, mid=2
  a[2]=18, key=18 == 18 → 查找成功，返回 2

比较次数：3 次

例题 2：构造判定树

有序数组 a[] = {11, 18, 25, 33, 46, 58, 69, 77}（$n=8$）

              33(3)
            /       \
        18(1)       58(5)
        /   \       /   \
    11(0)  25(2)  46(4)  69(6)
                            \
                            77(7)

括号中为数组下标。

例题 3：计算 ASL

查找成功的 ASL：

第 1 层（1 个结点）：33，比较 1 次
第 2 层（2 个结点）：18, 58，比较 2 次
第 3 层（4 个结点）：11, 25, 46, 69，比较 3 次
第 4 层（1 个结点）：77，比较 4 次

ASL = (1×1 + 2×2 + 4×3 + 1×4) / 8
    = (1 + 4 + 12 + 4) / 8
    = 21 / 8
    = 2.625

查找失败的 ASL：

判定树共有 $n+1 = 9$ 个外部结点（失败位置）。结合上面的判定树结构（77 位于第 4 层，其下还有 2 个外部结点），统计各外部结点所在层与比较次数：

外部结点位置	所在层	比较次数
11 的左右孩子	第 3 层	3
25 的左右孩子	第 3 层	3
46 的左右孩子	第 3 层	3
69 的左孩子	第 3 层	3
77 的左右孩子	第 4 层	4

即 7 个外部结点比较 3 次、2 个比较 4 次：

$$ASL_{失败} = \frac{7\times 3 + 2\times 4}{9} = \frac{29}{9} \approx 3.22$$

时间 / 空间复杂度 ▾

操作	时间复杂度	说明
查找成功（最好）	$O(1)$	第一次就找到（恰好是中间元素）
查找成功（最坏）	$O(\log_2 n)$	查找路径长度 = 树的高度
查找成功（平均）	$O(\log_2 n)$	约 $\log_2 n - 1$ 次比较
查找失败	$O(\log_2 n)$	到达外部结点的路径长度

关键数据：

n 个元素的折半查找判定树高度 $h = \lfloor\log_2 n\rfloor + 1$
最多比较 $\lfloor\log_2 n\rfloor + 1$ 次（等于树高）
平均比较次数约 $\log_2 n - 1$ 次

空间复杂度：$O(1)$（非递归版），$O(\log_2 n)$（递归版的栈空间）

与其他查找方法对比

方法	平均时间	要求
顺序查找	$O(n)$	无
折半查找	$O(\log_2 n)$	有序 + 顺序表
分块查找	$O(\sqrt n)$	分块有序
BST 查找	$O(\log_2 n)$（平均）	BST 结构
哈希查找	$O(1)$（平均）	哈希表

常见考法 ▾

手算折半查找过程：给定数组和目标值，写出每步的 low, high, mid 及比较结果（最常考）
画出折半查找判定树
计算 ASL（成功/失败）
判定树的性质：高度、结点数、外部结点数
折半查找与顺序查找的对比
折半查找只适用于顺序表，不适用于链表——为什么？
mid 的取法对判定树的影响（向下取整 vs 向上取整）

易错点 ▾

注意

循环条件是 low <= high：不是 low < high。当 $low == high$ 时，仍需比较一次（可能恰好找到）。
折半查找不能用于链表：因为需要通过下标直接访问 mid 元素，链表不支持随机访问，定位 mid 需要 $O(n)$ 时间，失去折半的意义。
数组必须有序：如果数组无序，折半查找的结果不可靠。
mid = (low + high) / 2 可能溢出：当 low 和 high 都很大时，low + high 可能超过 int 范围。安全写法：$mid = low + (high - low) / 2$。408 考试一般不考虑溢出问题。
判定树的外部结点数 = n + 1：n 个元素之间有 n-1 个间隔，加上首尾两端，共 n+1 个可能的失败位置。
折半查找判定树是平衡的但不一定是完全二叉树：当 n 不是 $2^k - 1$ 时，最后一层不完整。
查找失败的比较次数看外部结点的层数：不是内部结点。

核心结论 ▾

折半查找要求有序 + 顺序表，时间复杂度 $O(\log_2 n)$。
判定树高度 = $\lfloor\log_2 n\rfloor + 1$，最多比较次数 = 树高。
判定树有 n 个内部结点（成功）和 n+1 个外部结点（失败）。
折半查找的效率远高于顺序查找 $O(n)$，但要求数据有序且支持随机访问。
折半查找的判定树等价于 BST 中按同样规则查找的路径。
平均查找长度 $ASL \approx \log_2(n+1) - 1$（成功）。

记忆卡片 ▾

折半查找的两个前提条件？

① 存储结构必须是顺序表（数组），支持随机访问；② 数据必须有序。

判定树的高度？最多比较几次？

高度 $h = \lfloor\log_2 n\rfloor + 1$。查找成功最多比较 h 次；失败最多也比较 h 次。

判定树有多少个外部结点？

n+1 个，代表 n+1 个可能的查找失败区间。

为什么折半查找不能用于链表？

需要下标直接访问 mid（O(1)），链表定位第 mid 个元素需 O(n)。

循环条件为什么是 low <= high？

当 $low==high$ 时仍可能恰好命中，需再比较一次。

平均查找长度 ASL？

成功约 $\log_2(n+1)-1$，失败约 $\log_2(n+1)$。

交互动画 · 折半查找过程 ▾

点击开始：在有序数组中折半查找 key = 18

点「下一步」或「播放」

折半查找（Binary Search）

速查 ▾

核心概念 ▾

前提条件

判定树

判定树的构造规律

算法步骤 ▾

标准流程

查找路径

平均查找长度（ASL）

代码实现（C 语言） ▾

递归版

非递归版

查找第一个 $\geq key$ 的位置（lower_bound）

查找第一个 $> key$ 的位置（upper_bound）

手算示例 ▾

例题 1：折半查找过程

例题 2：构造判定树

例题 3：计算 ASL

时间 / 空间复杂度 ▾

与其他查找方法对比

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · 折半查找过程 ▾

相关知识点