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

Question

在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值21，所需的关键码比较次数为（ ）。A．2B．3C．4D．5

Answer 1

正确答案：A
基本思想：首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 　　重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。首先将顺序表一分为二，将21与中间值15进行比较，比15大，再将21与大于15的部分进行比较，即21与中间值21进行比较，刚好相等。