题目

已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多是( )。

错因

A

混淆了"成功查找"和"失败查找"的比较次数。n=16 时，成功查找的最大比较次数 = ⌊log₂16⌋ + 1 = 5，失败查找在某些路径下还需再比较一次（在叶节点处确认不匹配），最大达到 5 次。选 A（4）来自 log₂16 = 4，漏了最后一次比较。

C

高估了比较次数。n=16 = 2⁴，折半查找判定树的高度是 4，外部节点（失败终止点）都位于第 5 层，最多需要 5 次比较，不会到 6 次。选 C 可能以为失败查找需要额外多走一层。

D

同样高估。7 次比较对应长度约 2⁶ = 64 的表，n=16 远不需要这么多。

总解析

折半查找的判定树：n=16 的有序表对应一棵满二叉树（16 = 2⁴，恰好是完全满的），高度 = 4。

成功查找：最多走到第 4 层的内部节点，比较 4 次后找到，最多 4 次。

失败查找：走到第 4 层的内部节点后，最后一次比较确认不匹配（key ≠ mid），再往下到空指针，共走过 4 层内部节点 = 5 次比较。

用路径追踪验证（查找比所有元素都大的值）：

步骤	子表范围	比较的元素位置
1	[1..16]	A[8]
2	[9..16]	A[12]
3	[13..16]	A[14]
4	[15..16]	A[15]
5	[16..16]	A[16]，>A[16]，子表为空，查找失败

共 5 次比较。n=16（2 的整次幂）时，所有失败路径恰好都需要 5 次，不多不少。

最终答案是 B（5）。