问题
单项选择题
在顺序表(8，11，15，19，25，26，30，33，42，48，50)中，用二分法查找关键码值20，需做的关键码比较次数是( )。
A．3
B．4
C．6
D．8
答案
参考答案：B
解析：
由题意可知，关键字20不在顺序表中，所以这次查找只能是一次失败的查找。对长度为n的线性表进行二分查找，若查找不成功，则给定值与[log2n]+1个关键字进行过比较。所以在查找关键字20的过程中比较次数为[log211]+1，即进行了4次比较。具体查找过程如图17-2所示。其中[]中是当前的检索范围，↑指示当前检索范围中位于中点位置上的元素。
第一次 [8 11 15 19 25 26 30 33 42 48 50]
↑
第二次 [8 11 15 19 25] 26 30 33 42 48 50
↑
第三次 [8 11 15 [19 25] 26 30 33 42 48 50
↑
第四次 [8 11 15 19 [25] 26 30 33 42 48 50
↑
图17-2 二分查找的过程