分块查找

Question

有一个2000项的表，更采用等分区间顺序查找的分块查找法，问：1、每块的理想长度是多少？2、分成多少块最为理想？3、平均查找长度是多少？4、若每块是20，ASL是多少？求详解，谢谢！

Answer 1

分块查找的平均查找长度包括索引表和分块内的两部分之和：索引表+块中
假设线性表长n，均匀分成m块，每块中记录个数s，则m =上取整(n/s)，在等概率查找的前提下：
如果约定在索引表中确定关键字所在的分块也是顺序查找，因为顺序查找的平均查找长度为(L+1)/2，则ASL = (n/s + s)/2 + 1。当s =根号(n)时，该和值有极小值：根号(n) + 1

因此：
如果索引表内也是顺序查找，则每块的理想元素个数是根号(2000)，约为44.7，近似为45，同样分块数量也是45，因此ASL=2*(45+1)/2= 46。
如果每块长20，则分块为2000/20=100块，按照上面的结果，则ASL = (100+1)/2 + (20+1)/2 = 61