分块查找又称为索引顺序查找,是顺序查找的一种改进,其性能介于顺序查找和对分查找之间。分块查找将线性表分成若干块,每一块中的元素存储顺序是任意的,但块与块之间必须按关键字大小有序排列。即前一块中的最大关键字值小于(或大于)后一块中的最小(或最大)关键字值。另外,还需要建立一个索引表,索引表中的一项对应线性表中的一块,索引项由关键字域和链域组成,关键字域存放相应块的最大关键字,链域存放指向本块第一个元素的指针。索引表按关键字值递增(或递减)顺序排列。
分块查找过程分为两步进行,首先确定待查找的元素属于哪一块,即查找其所在的块;然后在块内查找要找的元素。由于索引表是递增有序的,因此可采用对分查找;而块内元素个数较少,在块内可采用顺序法查找。在块内的顺序查找不会对执行速度有太大的影响。
【例7-3】给定关键字序列如下:18,7,26,34,15,42,36,70,60,55,83,90,78,72,74,假设m=3,s=5,即将该序列分成3个表,每个子表有5个元素,则得到主表和索引表如图7-4所示。
图7-4 分块查找的主表和索引表
假设在上述表中查找“60”,则可以先在索引表中查找“60”所在的子表,由于34≤60≤70,故“60”应在第二块,这时start=5,length=5,因此,“60”应在主表的第5个位置~第9个位置之间查找。
分块查找的运算如下(在线性表R和含m个元素的索引表中分块查找关键字为k的元素,若查找到,则返回其序号i;若未查找到,则返回-1):
int BlkSearch(LineList R[ ],IDXType idx[ ],int m,KeyType k)
{
int low=0,high=m-1,mid,i,j,find=0;
while(low<=high && !find) /*对分查找索引表*/
{
mid=(low+high)/2;
if(k<idx[mid].key)
high=mid-1;
else if(k>idx[mid].key)
low=mid+1;
else
{
high=mid-1;
find=1;
}
}
if(low<m) /*k小于索引表内最大值*/
{
i=idx[low].low; /*在索引表中定块起始地址*/
j=idx[low].high; /*在索引表中定块终止地址*/
}
while(i<j && R[i].key!=k) /*在指定的块内采用顺序方法进行查找*/
i++;
if(i>=j)
return(-1);
else
return(i);
}
算法分析:分块查找实际上进行两次查找,整个算法的平均查找长度是两次查找的平均查找长度之和。
假设有n个元素,分成bn块,每块有s个元素,即bn=n/s,每块的查找概率为1/bn,块内每个元素的查找概率为1/s。平均查找长度为:
ASL≈log2(bn+1)-1+(s+1)/2≈log2(n/s+1)+s/2
分块查找的优点是:在线性表中插入或删除一个元素时,只要找到相应的块,然后在该块内进行插入或删除即可。由于块内元素个数相对较少,而且是任意存放的,所以插入或删除操作比较容易,不需要移动大量的元素。