8.3　分块查找

分块查找又称索引顺序查找,是顺序查找和折半查找的一种结合。

1.分块查找的基本思想

将具有n个元素的主表分成m个块（也称为子表）,每块内的元素可以无序,但要求块与块之间必须有序,并建立索引表。索引表包括两个字段:关键字字段（存放对应块中的最大关键字值）和指针字段（存放指向对应块的首地址）。

2.分块查找步骤

（1）在索引表中检测关键字字段,以确定待查找值k所处的分块（可用折半查找）位置。

（2）根据索引表指示的首地址,在该块内进行顺序查找。设关键字集合为90,43,14,30,78,8,62,49,35,71,22,80,18,52,85,按关键字值31,62,90分为三块建立的查找表及其索引表如下（见图8－3）。

线性表被分为3块（即三个子表）,每个块中有五个记录。表中的关键字值用数组A[i].key表示,其中,i为记录的顺序号。在索引表中有序地存放每块的最大关键字值30、62、90。若给定k的值为49,那么首先将k值与索引表中的索引值进行比较,由于30＜k＜62,因此可以确定该值在第二个块中。由于k值所在的块的地址指针指向块内第一个记录,即线性表中序号为5的记录,则k值应在表中序号为6到10之间,若在该块中找到该值则查找成功。

图8－3　分块有序表的索引存储

3.分块查找性能分析

分块查找由索引表查找和子表查找两步完成。设n个数据元素的查找表分为m个子表,并且每个子表均有t个元素,则t＝n/m。这样,分块查找的平均查找长度公式如下。

可见,平均查找长度不仅与表的总长度n有关,而且与所分的子表个数m有关。对于表长n确定的情况下,当m取时,ASL＝＋1达到最小值。

若用折半法查找确定关键字所在块时,则分块查找成功时的平均查找长度公式如下。