问题
单项选择题
对具有n个元素的有序序列进行二分查找时,()
A.查找元素所需的比较次数与元素的位置无关
B.查找序列中任何一个元素所需要的比较次数不超过log2(n+1)
C.元素位置越靠近序列后端,查找该元素所需的比较次数越少
D.元素位置越靠近序列前端,查找该元素所需的比较次数越少
答案
参考答案:B
解析:
二分查找是充分利用了元素间的次序关系,采用分治策略。它的基本思想是,将 n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2]则我们只要在数组a的右半部继续搜索x。 在二分查找中,查找元素所需的比较次数与元素的位置有关,选项A的说法错误。元素位置越靠近序列后端或前端,查找该元素所需的比较次数越多,选项C和选项D的说法错误。 选项B的说法正确,本题正确答案为选项B。