Appearance
分块查找（索引顺序查找）
为什么需要分块查找
顺序查找简单但效率低（O(n)），折半查找效率高但要求表必须有序且顺序存储。实际场景中，数据往往无法完全排序，但可以做到"大致有序"——这就是分块查找的用武之地。
分块查找是顺序查找和折半查找的折中方案：对索引表可用折半查找提高效率，块内仍用顺序查找保持灵活性。408 考研中，分块查找的 ASL 计算和最优分块大小是常见考点。
核心思想
将长度为 n 的查找表均匀分成 b 个块，每块含 s 个元素（n = b × s）。同时建立一个索引表，每个索引项记录对应块的最大关键字和块的起始地址。
分块查找的核心性质——块间有序、块内无序：
- 块间有序：第 i 块中的所有元素均小于第 i+1 块中的所有元素
- 块内无序：每一块内部的元素可以是无序的
数据的逻辑结构示意：
索引表: [max₁, addr₁] [max₂, addr₂] [max₃, addr₃]
↓ ↓ ↓
数据表: [ 块1: 无序 ] [ 块2: 无序 ] [ 块3: 无序 ]
约束: 块1所有元素 ≤ max₁ < 块2所有元素 ≤ max₂ < 块3所有元素 ≤ max₃交互可视化
通过下方的交互动画，你可以逐步观察分块查找的执行过程：
操作详解
索引表结构
索引表中每个索引项包含两个字段：
| 字段 | 含义 |
|---|---|
| maxKey | 该块中的最大关键字 |
| addr | 该块在查找表中的起始位置 |
索引表按 maxKey 递增排列，因此索引表本身是有序的，可以使用折半查找。
c
// 索引表项定义
typedef struct {
int maxKey; // 块内最大关键字
int addr; // 块的起始下标
} IndexItem;查找过程
分块查找分为两步：
第一步：确定目标所在的块
在索引表中查找第一个 maxKey ≥ key 的索引项，从而确定目标元素所在的块。这一步可用顺序查找或折半查找。
第二步：在块内顺序查找
在确定的块内，从起始位置开始逐个比较，直到找到目标元素或遍历完该块。
c
// 分块查找（索引表用折半查找，块内用顺序查找）
int blockSearch(int A[], int n, IndexItem idx[], int b, int key) {
// 第一步：折半查找索引表，确定所在块
int lo = 0, hi = b - 1, blockIdx = -1;
while (lo <= hi) {
int mid = (lo + hi) / 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; // 未找到
}ASL 分析
设查找表长度为 n，均匀分为 b 个块，每块 s 个元素（n = b × s）。假设查找每个元素的概率相等。
情况一：索引表和块内均用顺序查找
$$ASL = L_I + L_S = \frac{b+1}{2} + \frac{s+1}{2} = \frac{b+s}{2} + 1$$
将 b = n/s 代入：
$$ASL = \frac{n/s + s}{2} + 1$$
由均值不等式，当 $s = \sqrt{n}$ 时 ASL 取最小值：
$$ASL_{min} = \sqrt{n} + 1$$
情况二：索引表用折半查找，块内用顺序查找
$$ASL = L_I + L_S = \lceil \log_2(b+1) \rceil + \frac{s+1}{2}$$
此时最优分块大小同样约为 $s = \sqrt{n}$。
复杂度分析
| 查找方式 | 时间复杂度 | 最优 ASL | 适用条件 |
|---|---|---|---|
| 顺序查找 | O(n) | (n+1)/2 | 无限制 |
| 折半查找 | O(log₂n) | log₂(n+1) | 有序 + 顺序存储 |
| 分块查找（顺序索引） | O(√n) | √n + 1 | 块间有序 |
| 分块查找（折半索引） | O(log₂b + s) | log₂(b+1) + (s+1)/2 | 块间有序 |
空间复杂度：O(b)，需要额外存储含 b 个元素的索引表。
考研高频考点
- ⭐ "块间有序、块内无序"的含义（选择题/判断题高频）
- ⭐ ASL 计算：索引表顺序查找 vs 折半查找两种情况（计算题必考）
- ⭐ 最优分块大小 s = √n 的推导与结论（填空题/选择题高频）
- ⭐ 分块查找 vs 顺序查找 vs 折半查找的性能与适用场景对比（简答题常考）
- 索引表的结构定义（最大关键字 + 起始地址）
- 分块查找失败时的处理逻辑