分块查找（索引顺序查找）

2026 大纲 六（三）分块查找法。

退一步换灵活性

折半查找要求全表有序，代价是插一个元素平均要移动一半元素，动态场景下用不了。顺序查找对结构毫无要求，代价是 $O(n)$。

分块查找卡在两者中间，做法是放弃"全表有序"这个强条件，只保留一半：

🔴 块间有序、块内无序：第 $i$ 块的最大关键字 < 第 $i+1$ 块的最小关键字；块内元素可以任意排列。

这一刀切得很划算，因为它把两个好处各留了一半：

• 块间有序让你能跳过整块——这是分块比顺序查找快的全部来源。
• 块内无序让插入删除不必移动元素——找到该去哪一块，往块内的空位一放就行。

教材把它总结成一句话：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

配套的结构是一张索引表，每项是 (该块的最大关键字, 块的起始地址)：

索引表:  [max₁, addr₁]  [max₂, addr₂]  [max₃, addr₃]
              ↓               ↓               ↓
数据表:  [ 块1: 无序 ]   [ 块2: 无序 ]   [ 块3: 无序 ]

约束:    块1 全部元素 ≤ max₁ < 块2 全部元素 ≤ max₂ < 块3 全部元素 ≤ max₃

为什么索引项存的是最大值而不是最小值？ 因为查找条件是"找第一个 $ma{x}_i\ge key$ 的索引项"，只需要看一项就能判断；若存最小值，就得同时看相邻两项才知道 $key$ 落在哪一块。

还有一个推论：索引表本身按 $max$ 递增，所以索引表是有序的、可以折半查找。

先动手看一眼

加载可视化中...

两阶段与代码

查找分两步：① 在索引表里定位块（顺序、折半都行）；② 块内查找。

⚠️ 第二步只能用顺序查找——块内是无序的，折半的前提不成立。这条约束在算 ASL 时会一直跟着你。

typedef struct {
    int maxKey;  // 该块内的最大关键字
    int addr;    // 该块在数据表中的起始下标
} IndexItem;

// 索引表用折半查找，块内用顺序查找；返回下标，-1 表示失败
int blockSearch(int A[], int n, IndexItem idx[], int b, int key) {
    int lo = 0, hi = b - 1, blockIdx = -1;
    while (lo <= hi) {                      // 找第一个 maxKey >= key 的索引项
        int mid = lo + (hi - lo) / 2;
        if (idx[mid].maxKey >= key) {
            blockIdx = mid;                 // 记下候选，继续往左找更小的下标
            hi = mid - 1;                   // "找第一个满足条件的位置"的标准写法
        } else {
            lo = mid + 1;
        }
    }
    if (blockIdx == -1) return -1;          // 所有块的最大值都比 key 小

    int start = idx[blockIdx].addr;
    int end = (blockIdx + 1 < b) ? idx[blockIdx + 1].addr : n;   // 下一块起点即本块终点
    for (int i = start; i < end; i++)
        if (A[i] == key) return i;
    return -1;      // 块内没有就一定不在表中——块间有序保证了这一点
}

⚠️ 最后那行 return -1 是重点：块内扫完就判失败，不去看下一块。这是"块间有序"这条约束的直接回报，也是分块查找相对纯顺序查找的全部性能来源。

ASL：两段串联，优化就是让两段平衡

$$ASL=L_I+L_S$$

$L_I$ 是索引表上定位块的比较次数，$L_S$ 是块内查找的比较次数——两段是串联的，加起来。

索引与块内都用顺序查找时（$b=n/s$ 为块数、$s$ 为块长）：

$$ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(\frac{n}{s}+s)+1$$

现在问：$s$ 取多少最省？

🔴 $s=\sqrt{n}$ 时 ASL 最小，最小值是 $\sqrt{n}+1$。

推导（均值不等式）：对正数 $\frac{n}{s}$ 与 $s$，

$$\frac{n}{s}+s\ge 2\sqrt{\frac{n}{s}\cdot s}=2\sqrt{n}$$

等号成立当且仅当 $\frac{n}{s}=s$，即 $s=\sqrt{n}$。代回得 $AS{L}_{min}=\frac{1}{2}\cdot 2\sqrt{n}+1=\sqrt{n}+1$。

极值点的含义值得单说：$\frac{n}{s}$ 是索引表长度、$s$ 是块长，一个随 $s$ 增大、一个随 $s$ 减小。$s$ 取小了索引表变长，$s$ 取大了块内扫得久——最优点就是让两段工作量相等（此时 $b=s=\sqrt{n}$）。这个理解比记公式管用，换成别的组合（比如索引折半、块内顺序）也照样能想清楚该往哪个方向调。

⚠️ 别丢那个 $+1$。 两个 $\frac{1}{2}$ 相加正好是 1，最优值是 $\sqrt{n}+\mathbf{1}$ 而不是 $\sqrt{n}$。不过要注意问法：题目问"每块应包含多少元素"时答的是 $s=\sqrt{n}$；问"最小 ASL 是多少"时才是 $\sqrt{n}+1$。

数值验证（$n=16$）：

块长 $s$	块数 $b$	$ASL=\frac{b+1}{2}+\frac{s+1}{2}$
1	16	$8.5+1=9.5$
2	8	$4.5+1.5=6$
4	4	$2.5+2.5=\mathbf{5}$
8	2	$1.5+4.5=6$
16	1	$1+8.5=9.5$

$\sqrt{16}+1=5$，与 $s=4$ 那一行完全吻合 ✓。两端 $s=1$ 与 $s=16$ 的 ASL 都是 9.5，正好退化成长度 16 的纯顺序查找（$\frac{17}{2}=8.5$）再加一层多余开销——分块分得不对就白分了，时间复杂度也从 $O(\sqrt{n})$ 退回 $O(n)$。

一次完整的两阶段演算（第一次学、或想手动模拟时展开）

18 个记录分成 3 块，每块 6 个（$n=18$、$b=3$、$s=6$），索引与块内均用顺序查找：

索引表:   [22, 起始 1]   [48, 起始 7]   [86, 起始 13]

数据表:   下标 1~6:   22  12  13   8   9  20      ← 块内乱序，但全部 ≤ 22
          下标 7~12:  33  42  44  38  24  48      ← 全部在 (22, 48]
          下标 13~18: 60  58  74  49  86  53      ← 全部在 (48, 86]

先验证块间有序：块 1 的最大值 22 < 块 2 的最小值 24 ✓；块 2 的最大值 48 < 块 3 的最小值 49 ✓。块内怎么乱都不影响这条约束。

查找 38（成功）

1. 查索引表：$38>22$（第 1 次比较）→ $38\le 48$（第 2 次比较）→ 确定在块 2；
2. 块内从下标 7 顺序扫：33（1 次）→ 42（2 次）→ 44（3 次）→ 38（4 次，命中）。

合计 $2+4=6$ 次比较。

查找 29（失败）

1. 查索引表：$29>22$、$29\le 48$ → 块 2（2 次比较）；
2. 块内从下标 7 扫到下标 12，6 个元素全部比完仍未命中（6 次比较）；
3. 到此即可判失败——不需要再去看块 1 和块 3。

合计 $2+6=8$ 次比较。

索引表改用折半查找：精确式、教材近似式与两种算法（题目让索引表折半时展开）

此时 $L_S$ 不变仍是 $\frac{s+1}{2}$，$L_I$ 换成折半查找在 $b$ 个索引项上的平均比较次数。按折半查找的结论 $L_I\approx {\log }_2(b+1)-1$，两段相加得精确形式：

$$ASL\approx {\log }_2(\frac{n}{s}+1)+\frac{s}{2}-\frac{1}{2}$$

教材把末尾这个 $-\frac{1}{2}$ 一并吸收进近似号，写成

$$ASL\approx {\log }_2(\frac{n}{s}+1)+\frac{s}{2}$$

这就是严蔚敏教材给出的形式——它是在"$L_I$ 本身已经是个近似式"的基础上再抹掉一个常数，所以拿它去对一道给了具体 $b$ 与 $s$ 的题，差个零点几很正常。⚠️ 不要把这个式子当成可以逐项核对的等式：要精确值就回到 $ASL=L_I+L_S$，$L_I$ 按索引表的判定树逐层数。

⚠️ 两种算法要分清：

写法	它是什么	什么时候用
$L_I={\log }_2(b+1)-1$	折半查找的平均比较次数（近似式）	求平均 ASL，且题目按近似式给答案
$L_I=\lceil {\log }_2(b+1)\rceil$	折半判定树的高度，即最坏比较次数	求"最多比较几次"；用它算出的是上界不是平均值

题目若给出具体的 $b$，最稳的做法是画出索引表的判定树逐层统计 $L_I$。例如 $b=4$ 时折半判定树各层结点数为 1、2、1，$L_I=\frac{1\times 1+2\times 2+3\times 1}{4}=2$，配上 $s=4$ 得 $ASL=2+2.5=4.5$——比顺序索引的 5 略好。

最优块长仍在 $\sqrt{n}$ 附近：$L_I$ 变成对数项后随 $b$ 增长很慢，最优 $s$ 会比 $\sqrt{n}$ 略大；但 408 范围内按 $s=\sqrt{n}$ 回答即可，教材也是在顺序索引的前提下给出这个结论的。

失败 ASL 的推法与一次逐入口累加（题目要求算失败 ASL 时展开）

教材只给了成功 ASL。框架是固定的：

一次失败查找的比较次数 = 索引表上定位块所用的比较次数 + 扫完整个块的 $s$ 次比较。 特殊情形：$key$ 大于全表最大值时，索引表全部比完就判失败，不进入任何块。

$n=16$、$s=4$、$b=4$，索引表 $maxKey$ 为 14、26、42、60，索引与块内均顺序查找：

失败入口	索引比较	块内比较	合计
$key\le 14$	1	4	5
$14<key\le 26$	2	4	6
$26<key\le 42$	3	4	7
$42<key\le 60$	4	4	8
$key>60$	4	0（无块可查）	4

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{5+6+7+8+4}{5}=\frac{30}{5}=6$$

这个数不必记，要记的是推法：先数清有几个互不等价的失败入口，再对每个入口把两段比较次数加起来。这正是《查找基本概念》里那条通用规则的应用。

三种方法的复杂度对照，以及分块的插入删除代价

查找方式	时间复杂度	最优 ASL	前提
顺序查找	$O(n)$	$\frac{n+1}{2}$	无
折半查找	$O({\log }_{2}n)$	$\approx {\log }_2(n+1)-1$	有序 + 顺序存储
分块查找（顺序索引）	$O(\sqrt{n})$	$\sqrt{n}+1$	块间有序
分块查找（折半索引）	$O({\log }_{2}b+s)$	$\approx {\log }_2(\frac{n}{s}+1)+\frac{s}{2}$	块间有序 + 索引表有序

$O(\sqrt{n})$ 是怎么来的：把 $s=\sqrt{n}$ 代进 $ASL=\frac{b+s}{2}+1$，两段各贡献 $\frac{\sqrt{n}}{2}$，合计 $\sqrt{n}+1$，量级即 $O(\sqrt{n})$。注意这是取最优块长时的量级。

空间复杂度 $O(b)$ 即索引表占用的额外空间，取最优块长时为 $O(\sqrt{n})$。

插入删除：只需 $O(1)$ 次元素移动——找到该去哪一块，往块内空位一放即可，可能需要更新该块的索引项。这正是它相对折半查找的核心优势。缺点是要额外维护一张索引表，且初始建表时要做一次排序。

考点速记

三条结论：

1. 块间有序、块内无序；块内只能顺序查找。
2. $ASL=L_I+L_S$，两段串联；优化的本质是让两段工作量相等。
3. 顺序索引时 $s=\sqrt{n}$ 最优，$AS{L}_{min}=\sqrt{n}+1$。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 求最优块长：给出表长（如 400）、说明"均匀分块""查找概率相同"、并指明索引表和块内都用顺序查找，问每块包含多少元素效率最高。直接答 $s=\sqrt{n}$——400 个元素每块 20 个。⚠️ 看清问的是块长（答 $\sqrt{n}$）还是最小 ASL（答 $\sqrt{n}+1$），两个数差 1，选项里常常都有。

易错：块内不能折半查找。 块内是无序的，看到"块内也采用折半"要先怀疑题面，或按题目特别说明的"块内也有序"处理。

易错：$s=\sqrt{n}$ 是块长不是块数（虽然最优时两者相等，都等于 $\sqrt{n}$）。题目若不是均匀分块，或索引用折半，这个等号就不成立了。

易错：$AS{L}_{min}=\sqrt{n}+1$，那个 $+1$ 别丢。 两个 $\frac{\cdot +1}{2}$ 各贡献 $\frac{1}{2}$。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）7.2.3 节「分块查找」，p197： 分块查找又称索引顺序查找，"性能介于顺序查找和折半查找之间"； 索引项包含"关键字项（其值为该子表内的最大关键字）和指针项（指示该子表的第一个记录在表中位置）"； "分块有序"的定义；以及"由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找， 亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找"。 同页给出 $AS{L}_{bs}=L_b+L_w$ 与顺序索引情形的展开式，并指出 "当 $s$ 取 $\sqrt{n}$ 时，$AS{L}_{bs}$ 取最小值 $\sqrt{n}+1$"。
• 同书 p198：折半索引情形的近似式 $AS{L}_{bs}\approx {\log }_2(\frac{n}{s}+1)+\frac{s}{2}$； 以及分块查找的优缺点——"在表中插入和删除数据元素时，只要找到该元素对应的块， 就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易， 无需进行大量移动……其缺点是：要增加一个索引表的存储空间并对初始索引表进行排序运算"。

相关知识

顺序查找（块内查找就是它）｜折半查找（索引表可用它）｜ 查找基本概念（数失败入口的方法是本篇失败 ASL 的依据）｜ B 树、B+ 树（把一级索引推广成多级、索引组织成平衡树；B+ 树的叶结点链是"块间有序"在外存上的极致形式）｜ 查找算法分析与对比（分块正好卡在顺序与折半之间）

相关文章

• 查找基本概念
• 顺序查找
• 折半查找（二分查找）
• 二叉排序树查找 → 见树章节
• 平衡二叉树查找 → 见树章节
• 红黑树查找 → 见树章节
• B 树
• B+ 树
• 哈希表：拉链法
• 哈希表：开放定址法
• 查找算法对比

交互体验

前往完整可视化页面 →

真题练习

相关真题（1题）

2025Q72分