问题
单项选择题
对n个元素的有序表A[1…n]进行二分(折半)查找(除2取商时向下取整),查找元素A[i](1≤i≤n)时,最多与A中的______个元素进行比较。
A.n
B.log2n-1
C.n/2
D.log2n+1
答案
参考答案:D
解析:
本题考查数据结构基础知识。
二分查找是一种效率较高的查找方法,在10个元素构成的有序表中进行二分查找的过程可用二分查找判定树表示,如下图所示:
其中,结点中的数字表示元素在表中的序号。以结点10为例,它所在的位置说明若要查找表中的第10个元素,则依次与第5个、第8个、第9个和第10个元素进行了比较。若有序表中有n个元素,则对其进行二分查找的判定树的高度为log2n+1(与具有n个结点的完全二叉树高度一样),因此,查找过程中最多与log2n+1个元素进行比较。