有一个长度为n的有序顺序表，采用折半查找，经过i次比较成功找到的最多元素个数是______。
A. 2^i
B. 2^i+1
C. 2^(i-1)
D. 2^i-1
经过 i 次比较成功找到元素，说明元素位于判定树的第 i 层（根节点为第1层）。
对于一棵二叉树（折半查找判定树是二叉树的一种特殊形式），第 i 层最多的节点数为 2^(i-1) 个（假设根节点在第1层）。
这意味着经过 i 次比较成功找到的元素最多有 2^(i-1) 个，因为这些元素对应着判定树第 i 层的节点，而第 i 层最多能容纳 2^(i-1) 个节点。
题目读着真别扭，应该为一个满二叉树的节点数
举例并不恰当，自己评估一下，应该是每次只能查到一个，怎么可能是2的幂次方呢？@admin
admin 回复 amden： 这个要仔细审一下题，题目的意思是最多能找到几个元素，可以看一下右上角解析，增加了一个推导过程
题目读着这么别扭，不能理解出题人想表达什么意思。
选项改一下吧
有一个长度为n的有序顺序表，采用折半查找，经过i次比较成功找到的最多元素个数是2^(i-1)。
C
（画图举例子既可以出来了...
用户登录可进行刷题及查看答案
（画图举例子既可以出来了，比如1 2 3 4 5，查找3，mid为3，比较一次就找到，找到的最多元素个数为1，就是3，再比如查找4，mid一开始在3处，然后在4处，比较成功，比较两次就找到，找到的最多元素个数为2）
经过1次折半查找最多能找到1个元素
经过2次折半查找最多能找到2个元素
经过3次折半查找最多能找到4个元素
...
经过n次折半查找最多能找到2^(n-1)个元素
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案