😜 分块查找

分块查找

算法思想

分块查找借鉴了二分查找与顺序查找

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

可以利用顺序查找或者二分查找确定查找元素所在的块，然后在块内使用顺序查找

索引表

             24       54       78    88
             0        6        9     12

0  1  2 3  4 5  6  7  8  9  10 11 12 13
24 21 6 11 8 22 32 31 54 72 62 78 88 83

可以利用顺序查找或者二分查找确定查找元素所在的块，然后在块内使用顺序查找

例如搜索72，先搜索索引，比24大，比54大，满足72<=78,在下标范围[9,12)中进行顺序查找，第一次即命中

时间复杂度分析

平均查找长度为平均索引查找长度加上平均块内查找长度，ASL=L1+Ls

• 将长度n的查找表均匀分为b块，每块有s个记录，二者都是用顺序查找,每个元素被查找的概率相等

ASL=L1+Ls= (b+1)/2 + (s+1)/2 = (s^2+2s+n)/2s

• 若s= √n，则平均查找长度取最小值1+√n,索引表采用二分查找，平均查找长度

ASL=L1+Ls=⌈log(b+1)⌉+(s+1)/2

空间复杂度分析

与建立索引表的规则息息相关，视情况而定，但一般为常数阶，如果块的大小为1，则退化为O(n)