LV030-分块查找

一、分块查找

1. 查找方法

分块查找，也叫索引顺序查找，算法实现除了需要查找表本身之外，还需要根据查找表建立一个索引表。

• 分块

设记录表长为 n ，将表的 n 个记录分成$b=[n/s]$个块，每块 s 个记录（最后一块记录数可以少于 s 个），即：

且表分块有序，即第 i（1 ≤ i ≤ b-1） 块所有记录的 key 小于第 i + 1 块中记录的 key ，但块内记录可以无序。

• 建立索引

每块对应一个索引项，其中$k_{max}$为该块内记录的最大 key ， link 为该块第一记录的序号（或指针）。

下面是一个实例：设表长为 n = 8 ，取 s = 3 ，$b=[8/3]=3$，即分为 3 块，每块 3 个元素，最后一块不足 3 个元素，只有两个元素。如下图所示：

若查找 k = 19 的记录，索引表是按照$k_{max}$有序的，可对其折半查找，而块内按顺序方法查找。

2. ASL

分块查找算法的运行效率受两部分影响：查找块的操作和块内查找的操作。查找块的操作可以采用顺序查找，也可以采用折半查找（会更好一些）。块内查找的操作采用顺序查找的方式。

相比于折半查找，分块查找时间效率上更低一些。相比于顺序查找，由于在子表中进行，比较的子表个数会不同程度的减少，所有分块查找算法会更优。

总的来说。分块查找的 ASL 介于顺序查找和二分查找之间。