查找——分块查找

大家好，想要了解完整的静态查找可以看一看前面的文章

1.3 分块查找

索引顺序表的查找若以索引顺序表表示静态查找表，则可用分块查找来实现。分块查找又称索引顺序查找。这种查找方法中除了表本身以外尚需建立一个索引表。

• 构造过程

如图所示，该表的构造过程是:把要查找的表分成长度相等的几个子表 (称为块)。对每个子表建立一个索引项，其中包括两项内容:关键字项(存放该块中最大的关键字)指针项(存放该块中第一个记录的地址)。索引表中关键字递增有序，表中记录可以有序，也可以无序。但块之间一定有序(即后一块中的最小关键字都大于前一块中的最大关键字)。

• 查找过程

查找过程分两步:首先在索引表中确定待查记录所在的块;然后，在块中按顺序查找。由于索引表中的关键字递增有序，且是顺序存储可以用折半查找。而块中记录只能用顺序查找。因此，分块查找算法是上述两种算法的简单合成。

• 平均查找长度

分块查找的平均查找长度为 ASL= Lь+Lw。

（其中 Lb 为确定待查记录所在块的平均查找长度，Lw 为在块中的平均查找长度。）

• 顺序查找确定所在块，则分块查找的平均查找长度为：

ASLbs = Lь+ Lw= (b+1)/2+ (s+1)/2=(n/s+s)/2+1。

将长度为 n 的表均匀地分成 b 块，每块含有 s 个记录，即 b=n/s;又假定表中每个记录的查找概率相同，即每块查找的概率为 1/b，块中每个记录的查找概率为 1/s。

• 折半查找确定所在块，则分块查找的平均查找长度为:

ASL≈log2 (n/s+1)+s/2

其中 n 为表的长度;s 为每块中含有记录的个数。