6.4 分块查找

6.4.1 分块查找的定义

分块查找，又叫索引顺序查找。

6.4.2 分块查找的实现的实现

算法思想：用一个索引表给数据归类。

算法过程： ①在索引表中确定待查记录所属的分块（可顺序、可折半） ②在块内顺序查找

uTools_1638257539381

用折半查找索引表：

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找

6.4.3 查找效率分析

uTools_1638258212238

uTools_1638258279430

6.4.4 分块查找的优化

上面的分块查找对插入删除不友好。

改进：索引表为顺序表，查找表为链表。

1638258852038