题目

已知查找表中有 400 个元素，查找元素概率相同。采用分块查找法且均匀分块。若采用顺序查找法确定元素所在块，且块内也采用顺序查找法，为效率最高，每块包含元素应为( )。

错因

A

凭"块要尽量小"的直觉选了块大小 8。代入 ASL 公式：块数 ，索引平均比较 ，块内平均比较 ，总 ，比最优解 21 高。"块小"会让块数变多，索引开销反而增加。

B

凭"100/10、400/40 这类整除好看"的直觉选了 10。代入：，索引平均 ，块内平均 ，总 ，仍非最优。问题不是"分得整齐"而是"块数与块大小要平衡"。

D

把"块数 = "的口诀里"块数"和"块大小"对换了，或者直接拿 凑了"块大小 25"。块大小 25 时：，索引平均 ，块内平均 ，总 ——只比最优略差，但偏离了等式 的精确条件。

总解析

思路：分块查找的平均查找长度 ，两段都用顺序查找时分别 各自长度的一半，需要使两者之和最小。

符号约定：设总元素数 ，块数 ，块大小 ，则 。

• 索引顺序查找：平均比较次数
• 块内顺序查找：平均比较次数

总平均查找长度：

最小化 ：由均值不等式 ，等号当且仅当 时成立。

代入 ：

此时 ，是 4 个选项中最小的。

最终答案是 C（每块 20 个元素）。