分块查找_分块查找的时间复杂度

一 概述

分块查找又称作索引顺序查找，它吸取了顺序查找和折半查找各自的有点，既有动态结构，又适于快速查找。

二 分块查找的基本思想

将查找表分为若干子块，块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各个块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找的过程可以分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找。

三 分块查找的平均查找长度

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。假设分块查找的平均查找长度为索引查找L1和块内查找L2之和，设长度为n的查找表均匀分为b块，每块中存在s个数据。

此时分块的平均查找长度为：L1+L2；

若块内和块间均采用顺序查找时的平均查找长度为L1+L2 = (b+1)/2 + (s+1)/2 

此时的b = n/s，L1+L2 = (s^2+2s+n)/2s，根据(a+b)^2>=4ab可得L1+L2的最小值为n^1/2 +1；

如块内采用顺序查找，块间采用折半查找时的平均查找长度为L1+L2 = [log2^(b+1)] + (s+1)/2