(57)王道数据结构-分块查找

基本概念

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。缩印表中保存每个分块的最大关键字和分块的存储区间。

具有块内无序、块间有序的特点

基本思想

将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

查找过程

• 第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表。
• 第二步是在块内顺序查找。

ASL

ASL = 查索引的平均查找长度 + 查分块的平均查找长度

分类

设n个记录，均匀分为b块，没块s个记录

顺序查找索引表

$$
ASL = \frac{b+1}{2} + \frac{s+1}{2}
$$

$$
当s = \sqrt{n}时，ASL_{min} = \sqrt{n} + 1
$$

折半查找索引表

$$
ASL = [log_2(b+1)] + \frac{s+1}{2}
$$

易错点

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