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

A.4 B.5 C.6 D.7

[tag_link]

正确答案：B

折半查找 在查找成功时进行的关键字比较次数最多为 ⌊ l o g 2 n ⌋ + 1 ，即判定树的高度；

折半查找法在查找不成功时进行的关键字比较次数最多为 ⌊ l o g 2 n ⌋ + 1 。

题中 n = 16 ,因此最多比较 ⌊ l o g 2 16 ⌋ + 1 = 5 次。

也可以画出草图求解。