数据结构-线性表的查找-分块查找
1.思路
分块有序,即分成若干子表,要求每个子表中的数值都比后一块中数值小(但子表内部未必有序)。
然后将各子表中的最大关键字构成一个索引表,表中还要包含每个子表的起始地址(即头指针)。
2.查找过程
- 对索引表使用折半查找法(因为索引表是有序表);
- 确定了待查关键字所在的子表后,在子表内采用顺序查找法(因为各子表内部是无序表);
3.性能分析
查找效率:ASL=Lb+Lw
Lb:对索引表查找的ASL
Lw: 对块内查找的ASL
ASL=log(n/s+1)+s/2
logn<=ASL<=(n+1)/2
s为每块内部的记录个数,n/s即块的数目
例如,当n=9,s=3时,ASL=3.5,折半法为3.1,顺序法为5