在顺序表(3,6,8,10,12,15,16,18,21,25,30)中,用二分查找关键码值12,所需的关键码比较次数为A.2B.

Question

在顺序表(3，6，8，10，12，15，16，18，21，25，30)中，用二分查找关键码值12，所需的关键码比较次数为

A．2

B．3

C．3或4

D．4

Answer 1

正确答案：C
解析：二分法查找是一种线性表查找方法，其基本方法是：首先要用要查找的关键码与线性表中间位置结点的关键码值进行比较，这个中间结点把线性表分为两个子表，比较相等则查找完毕，不等则根据查找结果确定下一步的查找应该在哪一个子表中进行，如此下去，直到找到满足条件的结点，或者确定表中没有这样的结点。用二分法查找关键码值11的顺序如下所示，其中C) 内为本次检索的子表，()内为该子表的中间结果。从图中可以看出，经四次查找后，找到关键码12。但是如果在第三次查找时，选择 12，则只需要三次查找。
  第一次：[3，6，8，10，12，(15)，16，18，21，25，30]
  第二次：[3，6，(8)，10，12]，15，16，18，21，25，30
  第三次：[3，6，[(10)，12]，15，16，18，21，25，30)
  第四次：[3，6，8，10，[(12)]，(15)，16，18，2l，25，30]查找失败。