问题
单项选择题
对长度为n的有序表进行二分(折半)查找时,无论查找指定的一个元素是否成功,最多只与表中的()个元素进行比较即可。
A.[log2n]-1
B.[log2n]+1
C.n/2
D.n-1
答案
参考答案:B
解析:
本题考查基本算法中的查找运算。
对长度为,2的有序表进行二分(折半)查找时,其查找过程可用一棵二叉树描述(折半查找判定树),其高度与n个结点构成的完全二叉树的高度相同(即[*]),查找过程中从根结点最多比较到二叉树的最高层结点,因此参与比较的元素个数不超过[*]。