题目

对含有 600 个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是( )。

错因

A

直接算 取下整。，，所以 ，向下取整得 9。但折半查找的最坏比较次数是判定树的高度——是 ，向上取整或加一，9 是少算了一次。

C

把""和""或者别的对数搞混了。，但有人会用平方根 / 三分查找等思路凑出 30 这个数。也可能把"30 的平方约等于 900 ≈ 600"做了一次错误的折中估算。无论如何，折半查找的最坏次数与 成线性关系，不可能是 30 量级。

D

把折半查找当成顺序查找——"最坏要全表扫描"。600 个元素顺序查找最坏 600 次，300 是平均；但这是顺序查找的复杂度。题目明确说"折半查找"，复杂度 ，绝不会到 。

总解析

思路：折半查找的最坏比较次数 = 判定树的高度（从根到最深叶子的边数 + 1，或等价地说"路径上的节点数"）。

公式：含 个元素的判定树，高度 。

代入 ：

直观理解：

		判定树高度
1	1	1
2	2	2
4	3	3
...	...	...
512	10	10
600	10	10
1023	10	10
1024	11	11

也可以记成 ：，结果一致。

最终答案是 B（10）。