Block Search

Idea

Block Search combines indexing + sequential scan for large ordered arrays split into blocks. Blocks are ordered by a key (e.g., max per block); inside each block elements are unordered. Locate block via index, then sequentially scan inside.

分块查找法演示

块1：

371

块2：

958

块3：

121511

下一步

When to use

• Large sequential tables
• Frequent lookups, few inserts/deletes

Algorithm

1. Split into $m$ blocks of size $k$ (last may be smaller).
2. Build index table storing max (or min) key per block.
3. Search: locate block via index, then scan inside.

Pseudo-code:

for i = 0 to m-1:
    if x <= index[i]:
        // sequential search in block i
        for j = block[i].start to block[i].end:
            if A[j] == x:
                return j
        break
return -1

Complexity

• Build index: $O(n)$
• Search: $O(\sqrt{n})$ (when block count and block size are both $\sqrt{n}$)

Exercises

Exercise 1

Briefly state block search idea and scenarios.

参考答案

思路：先索引定位块，再块内顺序查。

步骤：

1. 分块，块内顺序；块间用索引
2. 适合大表、查找频繁、更新少

答案：分块+索引，适合大表。

Exercise 2

100 elements, 10 blocks of 10. Max comparisons?

参考答案

思路：索引 + 块内。

步骤：

1. 索引最多 10 次
2. 块内最多 10 次
3. 总计 20 次

答案：最多 20 次。

Past exam

2018·408

分块查找过程两步？效率？

参考答案

思路：索引定位 + 块内顺序；效率 $\sqrt{n}$。

步骤：

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

答案：两步，效率 $O(\sqrt{n})$。

PreviousSequential SearchSequential search basics, algorithm flow, complexity, and practice. NextBinary SearchBinary search basics, algorithm flow, complexity, and practice.