问题
单项选择题
对n个元素的有序表A[1..n]进行二分(折半)查找,则成功查找到表中的任意一个元素时,最多与A中的()个元素进行比较。
A.n-1
B.n/2
C.[log2n]−1
D.[log2n]+1
答案
参考答案:D
解析:
本题考查二分查找方法。
以10个元素为例,其二分查找的过程可以用以下二叉树表示(称为二分查找判定树,节点中的数字表示元素的序号):
由该例可以推广得知,n个节点的二分查找判定树的高度为[*],因此有序表中参与比较的元素个数最多为[*]。