考研全科复习资料

408

数据结构

分块查找

定位信息

项目	内容
章节	第六章查找 · 6.2
知识单元编号	DS-06-02
核心概念	分块查找（索引顺序查找）、块间有序、块内无序
前置知识	顺序查找、折半查找
考试权重	★★（选择题常见，综合题偶有涉及）

知识点讲解

一、分块查找的基本思想

分块查找（Blocking Search / Index Sequential Search）是介于顺序查找和折半查找之间的一种查找方法，兼顾了顺序查找的灵活性和折半查找的高效性。

核心规则：

将长度为 n 的表均匀地分为 b 块（Block），每块包含 s = ⌈n/b⌉ 个元素；
块间有序：第 i 块中所有元素的关键字 ≤ 第 i+1 块中所有元素的关键字（即块的最大关键字递增）；
块内无序：同一块内的元素不要求有序。

查找过程（两阶段）：

第一阶段——定块： 在索引表中确定目标关键字所属的块。索引表记录每块的最大关键字和起始地址。可用顺序查找或折半查找定位块。
第二阶段——块内顺序查找： 在目标块内用顺序查找定位具体元素。

二、索引表的结构

索引表是一个辅助数组，每个索引项包含两个字段：

maxkey：该块中的最大关键字
start：该块在主表中的起始下标

索引表 Index[b]:
┌──────────┬──────────┐
│  maxkey  │  start   │
├──────────┼──────────┤
│   22     │    1     │  ← 第 1 块：R[1..3]
│   48     │    4     │  ← 第 2 块：R[4..6]
│   86     │    7     │  ← 第 3 块：R[7..10]
└──────────┴──────────┘

三、ASL 分析

设表长 n，分为 b 块，每块 s 个元素：

索引表用顺序查找定块： ASL = (b+1)/2 + (s+1)/2
索引表用折半查找定块： ASL = ⌈log₂(b+1)⌉ + (s+1)/2 - 1

最优分块策略： 当 s = √n 时，总 ASL 最小，约为 √n + 1。

四、分块查找伪代码（C 风格）

// 索引项结构
typedef struct {
    KeyType maxkey;  // 该块最大关键字
    int start;       // 该块起始下标
} IndexItem;

// 分块查找：在主表 R[1..n] 中查找 key
// Index 为索引表，b 为块数
int BlockSearch(SqList R[], IndexItem Index[], int b, KeyType key) {
    // === 第一阶段：在索引表中顺序查找，确定所在块 ===
    int i = 1;
    while (i <= b && key > Index[i].maxkey)
        i++;                            // 找到第一个 maxkey >= key 的块
    if (i > b) return 0;               // 超出范围，查找失败

    // === 第二阶段：在第 i 块内顺序查找 ===
    int start = Index[i].start;
    int end = (i < b) ? Index[i+1].start - 1 : n; // 确定块的结束位置
    for (int j = start; j <= end; j++) {
        if (R[j].key == key)
            return j;                   // 查找成功
    }
    return 0;                           // 块内未找到，查找失败
}

五、三种查找方法对比表

对比维度	顺序查找	折半查找	分块查找
存储结构	顺序表 / 链表	仅顺序表	顺序表 + 索引表
有序要求	无	全表有序	块间有序，块内无序
ASL（等概率）	(n+1)/2	≈ log₂(n+1)-1	√n + 1（最优）
时间复杂度	O(n)	O(log n)	O(√n)
动态插入删除	容易	困难（需移动元素）	块内容易，块间较难
适用场景	小规模 / 无序	大规模有序	中等规模，允许块内无序

记忆辅助

"块间有序块内乱，先定块来再线查" — 分块查找分两步：先在索引表定块，再在块内顺序查找。
"√n 最优分，ASL 最小值" — 每块 √n 个元素、共 √n 块时，ASL 最小。
"索引能折半，块内只能顺序" — 索引表有序可以用折半查找加速定块过程。
"折半查不了链表，分块查不了链表索引" — 分块查找的主表需要顺序存储以支持块内顺序查找的高效访问。

例题精解

例题 1：分块查找 ASL 计算

将长度 n = 18 的表分为 3 块，每块 6 个元素。索引表用顺序查找定块，块内用顺序查找。等概率情况下，求成功查找的 ASL。

解题四步法：

① 审题： n=18, b=3 块, s=6 个/块，索引和块内均用顺序查找。

② 分析： ASL = 定块的 ASL + 块内查找的 ASL。

③ 计算：

定块 ASL（索引表顺序查找）= (b+1)/2 = (3+1)/2 = 2
块内 ASL（顺序查找）= (s+1)/2 = (6+1)/2 = 3.5
总 ASL = 2 + 3.5 = 5.5

④ 结论： 成功查找的 ASL = 5.5。若改为每块 √18 ≈ 5 个元素（约 4 块），ASL 会更小。

例题 2：分块查找过程模拟

给定主表 R = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53}（下标 1~18），分为 3 块，索引表为 {{22,1}, {48,7}, {86,13}}。查找 key = 60。

解题四步法：

① 审题： 主表分为 3 块，索引表记录每块最大关键字和起始位置，查找 key = 60。

② 分析： 先在索引表中确定 60 所属的块，再在块内顺序查找。

③ 过程：

定块： 比较索引表：
- 60 > 22（第 1 块最大值）→ 继续
- 60 > 48（第 2 块最大值）→ 继续
- 60 ≤ 86（第 3 块最大值）→ 确定在第 3 块
- 定块比较次数 = 3
块内查找（第 3 块：R[13..18] = {60, 58, 74, 49, 86, 53}）：
- R[13] = 60 == 60 → 成功！
- 块内比较次数 = 1
总比较次数 = 3 + 1 = 4

④ 结论： 查找 key=60 共需 4 次比较，查找成功。

考情分析

维度	说明
考频	中等偏低，选择题为主
题型	选择题（ASL 计算、查找过程分析）、偶尔综合题
命题趋势	与顺序查找、折半查找对比出题；考查最优分块策略
常见陷阱	ASL 公式中 b 和 s 的含义混淆；忘记最优分块是 s=√n

易错点

索引表的 maxkey 是块内最大关键字，不是最后一个元素的关键字！ 块内无序时，最大值可能在块中任意位置。
ASL = 定块 ASL + 块内 ASL，两者分别用顺序/折半查找独立计算。 定块和块内可以选择不同的查找方法。
最优分块 s = √n 时，总 ASL ≈ √n + 1，这是理论最小值。 实际中 b 和 s 应为整数，需要取整处理。
分块查找不能用于链表主表（需要按下标随机访问块内元素），但索引表本身是顺序表，不影响。

来源标注

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

408 ​

数据结构 ​

分块查找 ​

408

数据结构

分块查找