分块查找法

定义与基本思想

分块查找法（Block Search）是一种结合顺序查找和索引查找的方法，适用于数据量较大的顺序表。其基本思想是：将表分为若干块，每块内元素无序，块间按某种规则有序，通过索引定位块，再在块内顺序查找。

适用场景

• 适用于数据量较大的顺序表
• 适用于查找频繁、插入删除较少的场合

算法描述

1. 将表分为 $m$ 块，每块 $k$ 个元素（最后一块可少于 $k$ 个）
2. 建立块索引表，记录每块的最大（或最小）关键字
3. 查找时，先在索引表中定位目标所在块，再在该块内顺序查找

伪代码如下：

for i = 0 to m-1:
    if x <= index[i]:
        // 在第i块内顺序查找
        for j = block[i].start to block[i].end:
            if A[j] == x:
                return j
        break
return -1

代码实现

// 分块查找：index[] 为索引表（每块最大关键字），start/end 为每块范围
int BlockSearch(int A[], int n, int blockSize, int index[], int m, int key) {
    int block = -1;
    // ① 在索引表中定位所在块（顺序查找）
    for (int i = 0; i < m; i++) {
        if (key <= index[i]) {
            block = i;
            break;
        }
    }
    if (block == -1) return -1;  // 超过所有块的最大值
    // ② 在块内顺序查找
    int start = block * blockSize;
    int end = (start + blockSize < n) ? start + blockSize : n;
    for (int j = start; j < end; j++) {
        if (A[j] == key) return j;
    }
    return -1;  // 查找失败
}

平均查找长度（ASL）推导

设表长 n 分为 m 块，每块长度 $s = \lceil n/m \rceil$。块间用索引（顺序查找），块内用顺序查找。

$ASL = ASL_{索引} + ASL_{块内} = \frac{m+1}{2} + \frac{s+1}{2}$

当 $m \approx s \approx \sqrt{n}$ 时（块数和块长都取 $\sqrt{n}$），ASL 取最小值：

$ASL_{min} = \sqrt{n} + 1$

这就是分块查找能达到 $O(\sqrt{n})$ 的原因。

时间复杂度分析

• 建立索引表：$O(n)$
• 查找：$O(\sqrt{n})$（通常块数和块长均为 $\sqrt{n}$）

习题

习题 1

简述分块查找法的基本思想，并说明其适用场景。

习题 2

某表有 $100$ 个元素，分为 $10$ 块，每块 $10$ 个元素。若查找某元素，最多需要比较多少次？

习题 3

分块查找法的查找过程包括哪两步？其查找效率如何？