对具有n个元素的有序序列进行二分查找时,(61)。A.元素位置越靠近序列前端,查找该元素所需的比较次

Question

对具有n个元素的有序序列进行二分查找时，(61)。

A．元素位置越靠近序列前端，查找该元素所需的比较次数越少

B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]

C．查找元素所需的比较次数与元素的位置无关

D．元素位置越靠近序列后端，查找该元素所需的比较次数越少

Answer 1

正确答案：B
解析：二分查找过程是：以处于中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或查找区间的大小为零时(表明查找不成功)为止。对于有11个元素的有序表进行二分查找的过程可用一个二叉树表示，如图6-12所示(结点中的数字表示元素在序列中的序号)。

图6-12所示二叉树表明，若需要查找序列中的第6个元素，则仅需一次元素间的比较。若需查找第3个或第9个元素，则分别需要两次比较。依此类推，查找第1、4、7、10个元素时，分别需要三次比较，查找第2、5、 8、11个元素时，分别需要四次比较。因此，查找元素所需的比较次数与元素在序列中的位置是有关的。显然，选项A或D的说法也是错误的。若序列中有n个元素，则根据二分查找法构造的二叉树的高度不会超过[log₂(n+1)]，因此选项B是正确的。