分块查找法

定义与基本思想

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

分块查找法演示

块1：

371

块2：

958

块3：

121511

下一步

适用场景

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

算法描述

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

时间复杂度分析

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

练习题

练习 1

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

参考答案

解题思路：考查分块查找的原理和应用。

详细步骤：

1. 将表分块，块内顺序查找，块间用索引定位
2. 适用于大表、查找频繁、插入删除少

答案：分块+索引，先定位块再顺序查找，适合大表。

练习 2

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

参考答案

解题思路：先查索引，再查块内。

详细步骤：

1. 最多查 $10$ 次索引，定位块
2. 块内最多查 $10$ 次
3. 总共最多 $10+10=20$ 次

答案：最多比较 $20$ 次。

考研真题

真题 1

【2018·408】分块查找法的查找过程包括哪两步？其查找效率如何？

参考答案

解题思路：分块查找的流程和效率。

详细步骤：

1. 先查索引表定位块
2. 再在块内顺序查找
3. 查找效率 $O(\sqrt{n})$

答案：两步：查索引、查块内。效率 $O(\sqrt{n})$。