考研全科复习资料

408

数据结构

顺序查找与折半查找

定位信息

项目	内容
章节	第六章查找 · 6.1
知识单元编号	DS-06-01
核心概念	顺序查找（线性查找）、折半查找（二分查找）、判定树
前置知识	线性表、二叉树基础
考试权重	★★★（高频基础考点）

知识点讲解

一、顺序查找（Sequential Search）

顺序查找是最基本的查找算法，从表的一端开始，逐个比较关键字，直到找到目标或遍历完整个表。适用于顺序表和链表，对存储结构无特殊要求，也不要求表有序。

基本思想： 从数组第一个元素开始，将每个元素的关键字与给定值 key 进行比较。若相等则查找成功，返回下标；若遍历到末尾仍未找到，则查找失败。

改进——设置哨兵： 在数组下标 0 处存放待查关键字 key，从后往前查找，可以省去每次循环中的越界判断 i >= 0，将循环条件简化为 R[i] != key。虽然时间复杂度不变，但实际运行速度提升约 50%。

平均查找长度（ASL）： 假设每个元素被查找的概率相等（等概率），成功时 ASL = (n+1)/2，失败时 ASL = n。若考虑不等概率，按查找概率从高到低排列可降低 ASL。

二、折半查找（Binary Search）

折半查找要求表采用顺序存储且关键字有序。每次将待查区间缩小一半，效率远高于顺序查找。

基本思想： 设查找区间为 [low, high]，取中间位置 mid = (low + high) / 2（下取整）。将 R[mid] 与 key 比较：

若 R[mid] == key，查找成功；
若 R[mid] > key，在左半区 [low, mid-1] 继续查找；
若 R[mid] < key，在右半区 [mid+1, high] 继续查找；
直到 low > high 时查找失败。

判定树： 折半查找的过程可以用一棵二叉树来描述，称为折半查找判定树。树中每个结点对应一次比较位置，根结点是第一次比较的 mid。判定树的形态只与表长 n 有关，与元素的具体值无关。

ASL 分析： 判定树的高度 h = ⌊log₂n⌋ + 1。查找成功时 ASL ≈ log₂(n+1) - 1；查找失败时 ASL 与失败结点数有关。

折半查找的伪代码（C 风格）：

// 在有序表 R[1..n] 中折半查找关键字 key
// 返回下标（成功）或 0（失败）
int BinarySearch(SqList R[], int n, KeyType key) {
    int low = 1, high = n;          // 初始化查找区间
    while (low <= high) {            // 区间非空时继续
        int mid = (low + high) / 2;  // 取中间位置（下取整）
        if (R[mid].key == key)       // 查找成功
            return mid;
        else if (R[mid].key > key)   // 目标在左半区
            high = mid - 1;
        else                         // 目标在右半区
            low = mid + 1;
    }
    return 0;                        // low > high，查找失败
}

三、对比表

对比维度	顺序查找	折半查找
存储结构	顺序表 / 链表均可	仅限顺序表
是否要求有序	无要求	必须有序
成功 ASL（等概率）	(n+1)/2	≈ log₂(n+1) - 1
时间复杂度	O(n)	O(log n)
适用场景	小规模 / 无序表 / 链表	大规模有序顺序表
是否可用于链表	✅	❌

记忆辅助

"顺序无所谓，折半要有序" — 顺序查找对表是否有序无要求；折半查找必须有序 + 顺序存储。
"折半看判定，高度是关键" — 判定树的高度 h = ⌊log₂n⌋ + 1，决定了查找的时间复杂度。
"哨兵省判断，效率翻一番" — 设置哨兵虽不改变 O(n)，但减少了一半的比较次数，实际速度约提升 50%。
"mid 下取整，low 和 high 二分收窄" — mid = (low + high) / 2，区间每轮缩小一半。

例题精解

例题 1：折半查找过程模拟

给定有序表 R = {5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92}（共 11 个元素，下标 1~11），用折半查找关键字 21，写出查找过程。

解题四步法：

① 审题： 在长度为 11 的有序表中折半查找 key = 21。

② 分析： 按照折半查找算法，逐步缩小查找区间。

③ 过程：

步骤	low	high	mid	R[mid]	比较
第 1 轮	1	11	6	56	56 > 21，high = 5
第 2 轮	1	5	3	19	19 < 21，low = 4
第 3 轮	4	5	4	21	21 == 21，✅ 成功

④ 结论： 经过 3 次比较，查找成功，返回下标 4。ASL 成功 = 3 次比较。

例题 2：折半查找判定树构造

对长度 n = 11 的有序表，画出折半查找判定树，求查找成功和失败的 ASL（等概率）。

解题四步法：

① 审题： 需要构造 n=11 的判定树并计算 ASL。

② 分析： 判定树中，第 i 层结点需要 i 次比较。n=11 的判定树是完全二叉树或接近完全二叉树。

③ 构造与计算：

判定树结构（层次遍历）：

         6          ← 第1层：1个结点，比较1次
       /   \
      3     9       ← 第2层：2个结点，比较2次
     / \   / \
    1   4 7   11    ← 第3层：4个结点，比较3次
     \   \ \    \
      2   5 8   10  ← 第4层：4个结点，比较4次

成功 ASL = (1×1 + 2×2 + 4×3 + 4×4) / 11 = (1 + 4 + 12 + 16) / 11 = 33/11 = 3

失败情况：判定树有 12 个外部结点（空指针），分布在第 3、4、5 层：

第 3 层失败结点：2 个，比较 3 次
第 4 层失败结点：6 个，比较 4 次
第 5 层失败结点：4 个，比较 5 次

失败 ASL = (2×3 + 6×4 + 4×5) / 12 = (6 + 24 + 20) / 12 = 50/12 ≈ 4.17

④ 结论： 成功 ASL = 3，失败 ASL ≈ 4.17。判定树高度为 4，与 ⌊log₂11⌋ + 1 = 4 一致。

考情分析

维度	说明
考频	顺序查找为选择题常考；折半查找为选择/综合题高频考点
题型	选择题（ASL 计算、比较次数判断）、综合题（判定树构造、查找过程模拟）
命题趋势	折半查找判定树的构造、成功/失败 ASL 计算是经典综合题型
常见陷阱	mid 下取整方向影响判定树形态；折半查找只能用于有序顺序表

易错点

折半查找只能用于顺序存储的有序表，不能用于链表！ 因为链表不支持随机访问，无法在 O(1) 时间内定位 mid。
mid 的取整方向会影响判定树形态。 (low+high)/2 是下取整，不同取整方式导致判定树不同，但不影响时间复杂度。
折半查找的 ASL 是 O(log n)，不是 O(n/2)。 与顺序查找本质区别在于每次将搜索区间减半。
判定树中失败结点的层数计算容易出错。 失败结点位于外部结点（空指针），比较次数等于其父结点的层数。

来源标注

来源	说明
王道考研	2026 版数据结构讲义 · 第六章查找
天勤考研	数据结构高分笔记 · 查找部分
严蔚敏	《数据结构（C 语言版）》第 9 章
教材参考	《数据结构》（第 5 版）李春葆 · 查找章节

408 ​

数据结构 ​

顺序查找与折半查找 ​

408

数据结构

顺序查找与折半查找