折半查找（二分查找）

为什么需要折半查找

顺序查找每次只能排除一个元素，效率低下。如果表本身是有序的，我们就可以利用有序性，每次比较直接排除一半的元素，大幅提升查找效率。

折半查找（又称二分查找）就是基于这一思想的经典算法。408 考研中，折半查找是查找章节的绝对核心，几乎每年必考，需要掌握算法流程、判定树构造、ASL 计算等全部内容。

前提条件：折半查找要求表必须是有序的顺序表（即用数组存储的有序序列）。

核心思想

折半查找的核心特点：

每次比较排除一半：将查找区间缩小为原来的一半
三个指针：用 low、high 标记当前查找区间，mid = (low + high) / 2 为中间位置
比较与缩小区间：将目标值 key 与 mid 位置元素比较，相等则查找成功；key 较小则在左半区间继续查找；key 较大则在右半区间继续查找
终止条件：low > high 时查找失败

交互可视化

通过下方的交互动画，你可以逐步观察折半查找的执行过程：

加载可视化中...

操作详解

算法思路

关键步骤：

初始化 low = 0，high = n - 1
计算 mid = (low + high) / 2（向下取整）
比较 key 与 a[mid]：
- 若 key == a[mid]，查找成功，返回 mid
- 若 key < a[mid]，令 high = mid - 1，在左半区间继续
- 若 key > a[mid]，令 low = mid + 1，在右半区间继续
重复步骤 2-3，直到 low > high，查找失败

代码实现：

// 折半查找（非递归）
// a[] 为有序数组（升序），n 为元素个数，key 为目标值
int BinarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == key)
            return mid;       // 查找成功
        else if (a[mid] > key)
            high = mid - 1;   // 在左半区间查找
        else
            low = mid + 1;    // 在右半区间查找
    }
    return -1;                // 查找失败
}

⭐ 注意 mid 的取整方向：(low + high) / 2 是向下取整（取左中位数）。不同取整方式会构造出不同的判定树，408 真题中经常以此设陷阱。

判定树构造

折半查找的过程可以用一棵判定树（也叫比较树）来描述。每个结点表示一次比较的中间元素 mid，左子树对应 key < a[mid] 的情况，右子树对应 key > a[mid] 的情况。

以有序表 {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43} （n = 11）为例，判定树如下：

                    [19]                ← 第 1 层
                  /       \
              [10]          [33]        ← 第 2 层
             /    \        /    \
           [7]   [13]   [29]   [41]    ← 第 3 层
             \     \      \    /  \
             ×    [16]   [32] [37] [43] ← 第 4 层

判定树的重要性质：

⭐ 判定树是一棵平衡二叉排序树（形态唯一，取决于 n 和取整方式）
⭐ mid = ⌊(low + high) / 2⌋ 时，若结点数为偶数，左子树结点数比右子树少 1（右子树更"胖"）；若为奇数则左右相等
树的高度 h = ⌈log₂(n+1)⌉
查找成功时的比较次数 = 该元素在判定树中的层数
查找失败时的比较次数 = 走到的外部结点（空结点）的父结点层数

ASL 计算

查找成功的 ASL

假设查找每个元素的概率相等（均为 1/n），则：

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

其中 $l_i$ 是第 i 个元素在判定树中的层数。

以上面 n = 11 的例子为例：

层数	结点	结点数
1	19	1
2	10, 33	2
3	7, 13, 29, 41	4
4	16, 32, 37, 43	4

$$ASL_{成功} = \frac{1 \times 1 + 2 \times 2 + 3 \times 4 + 4 \times 4}{11} = \frac{1 + 4 + 12 + 16}{11} = \frac{33}{11} = 3$$

⭐ 通用公式（n 较大时的近似值）：$ASL_{成功} \approx \log_2(n+1) - 1$

查找失败的 ASL

查找失败时，查找路径终止于判定树的外部结点（即空指针位置，共 n+1 个）。每个外部结点对应一个失败的查找区间，比较次数等于其父结点的层数。

仍以 n = 11 为例，外部结点共 12 个：

父结点层数	外部结点数
3	1
4	11

这里第 3 层的结点 7 只有右子树没有左子树的空位贡献 1 个第 3 层外部结点，其余外部结点均在第 4 层。

$$ASL_{失败} = \frac{3 \times 1 + 4 \times 11}{12} = \frac{3 + 44}{12} = \frac{47}{12} \approx 3.92$$

⭐ 408 考试中 ASL 计算是高频大题，务必能够根据给定序列手画判定树，然后逐层统计结点数。

复杂度分析

指标	复杂度	说明
最好时间复杂度	O(1)	第一次比较就命中（mid 恰好是目标）
最坏时间复杂度	O(log₂n)	比较次数等于判定树高度 ⌈log₂(n+1)⌉
平均时间复杂度	O(log₂n)	ASL ≈ log₂(n+1) - 1
空间复杂度	O(1)	仅需 low、high、mid 三个辅助变量

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

折半查找的关键在于需要随机访问 a[mid]，即通过下标直接定位中间元素（O(1) 时间）。链表不支持随机访问，访问第 mid 个结点需要从头遍历，时间为 O(n)，这会使折半查找退化为比顺序查找更慢的算法，失去意义。因此折半查找仅适用于顺序表（数组）。

考研高频考点

⭐ 给定有序序列，手动画判定树并计算成功 / 失败 ASL（大题高频，几乎每年必考）
⭐ 折半查找的适用条件：有序 + 顺序存储（选择题高频陷阱）
⭐ 判定树的形态与 mid 取整方式的关系（向下取整 vs 向上取整构造不同的树）
⭐ 折半查找的时间复杂度 O(log₂n) 及其推导
折半查找与二叉排序树的对比（判定树是平衡 BST）
折半查找失败时比较次数的计算（外部结点分析）
为什么链表不适用折半查找（随机访问特性）

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

折半查找（二分查找） ​

为什么需要折半查找 ​

核心思想 ​

交互可视化 ​

操作详解 ​

算法思路 ​

判定树构造 ​

ASL 计算 ​

查找成功的 ASL ​

查找失败的 ASL ​

复杂度分析 ​

考研高频考点 ​

相关文章