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