首页 > 试题广场 >

采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长

[单选题]

采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为()

  • O(n^2)
  • O(nlog2n)
  • O(n)
  • O(log2n)
推荐
选D。
二分查找方法的思想:将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小 于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。
  • 最好的情况是:待查关键字刚好位于序列中间,第一次即查到。
  • 最坏的情况是第一次查找,还剩下n/2个元素需要比较;第二次,还剩n/4……第i次查找,还剩下n/2i个元素需要比较,直到剩余最后一个元素,查找结束。
最后n/2i=1,即n=2i,i为查找的次数(长度),i=log2n,所以选D。
编辑于 2019-07-15 14:22:07 回复(0)
该题重点是平均,如果问的是最坏情况下,查找长度是多少,毫无疑问n=2x,即x=log2n。
怎么理解平均呢,就是所有长度之和/n:
(log2n+log2(n-1)+log2(n-2)+...+log21)/n=log2n*(n-1)...*1/n=log2n!/n
好了,我卡住了
发表于 2020-06-19 16:06:31 回复(0)
但是书上?

发表于 2022-08-21 12:02:54 回复(0)
答案有问题吧,问的是平均啊!不是最多啊!
发表于 2020-08-16 10:49:48 回复(0)
最坏的情况n/2i=1,即n=2i,i为查找的次数(长度),i=log2n
最好的情况直接就是1次
综上,本题选择D项

发表于 2020-06-15 15:09:32 回复(0)
D:其查找过程描述的判定树高度,等于n个结点的完全二叉树的高度,平均性能也是O(log2n)
发表于 2019-07-12 15:37:00 回复(0)
D, 首先二分法,切一半,再去查找下一次,这样A排除了。采用二分的前提是数据有序,因此另外一半不用考虑了,只查另外一半,逐次执行砍掉一半数据规模,因此B、C都排除了。比如数据规模是 n,执行一次n/2的数据规模,再继续执行一次,n/2/2,第三次 n/2/2/2, 因此可以看出来应该是log2n的时间复杂度去查找。
发表于 2019-07-13 20:39:03 回复(0)
找一个小于n级别的
发表于 2020-03-20 06:35:21 回复(0)