分块查找

分块查找（Blocking Search / Index Sequential Search）是介于顺序查找和折半查找之间的一种查找方法。

基本思想

1. 将表分成若干块（Block）
2. 块内可以无序
3. 块间必须有序（第 i 块的最大值 < 第 i+1 块的最小值）
4. 建立索引表，记录每块的最大关键字和起始地址

存储结构

// 索引表项
typedef struct {
    IndexType maxValue;  // 块内最大关键字
    int start;           // 块的起始位置
    int length;          // 块的长度
} IndexItem;

// 主表 + 索引表
IndexItem index[MAX_BLOCKS];  // 索引表
ElemType data[MAX_SIZE];       // 主表

图示

索引表：
┌─────────────────────────────────┐
│ maxValue=25, start=0, length=5  │  块1
│ maxValue=50, start=5, length=5  │  块2
│ maxValue=75, start=10, length=5 │  块3
└─────────────────────────────────┘

主表（块内无序，块间有序）：
块1: [22, 13, 25, 8, 17]    块1最大值=25
块2: [45, 32, 50, 38, 41]   块2最大值=50
块3: [63, 75, 58, 70, 66]   块3最大值=75

示例一：计算 ASL

有 16 个元素，分成 4 块，每块 4 个元素。用顺序查找做索引查找，求 ASL。

• 索引表 ASL：$(4+1)/2 = 2.5$
• 块内 ASL：$(4+1)/2 = 2.5$
• 总 ASL：$2.5 + 2.5 = 5$

示例二：最优分块

有 100 个元素，如何分块使 ASL 最小（索引表顺序查找）？

分析：$ASL = b/2 + s/2 + 1$，约束条件 $b \times s = 100$。

用均值不等式：$b + s \geq 2\sqrt{bs} = 2\sqrt{100} = 20$。

当 $b = s = 10$ 时取等号，此时 ASL = $10/2 + 10/2 + 1 = 11$。

示例三：分块查找过程

在上面的示例表中查找 58。

1. 查索引表：
   - 25 < 58，继续
   - 50 < 58，继续
   - 75 ≥ 58，在块 3 中
2. 在块 3 [63, 75, 58, 70, 66] 中顺序查找：
   - 63 ≠ 58
   - 75 ≠ 58
   - 58 = 58，找到！
比较次数：索引表 3 次 + 块内 3 次 = 6 次

示例四：索引表折半查找

索引表有 7 项，用折半查找确定块号，然后在块内顺序查找（块大小 8），求最坏情况比较次数。

• 折半查找最坏：$\lfloor\log_2 7\rfloor + 1 = 3$ 次
• 块内顺序查找最坏：8 次
• 最坏总比较次数：$3 + 8 = 11$ 次