i3geek.com
闫庚哲的个人博客

二分查找的时间复杂度,最大查找次数

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

时间复杂度


假设其数组长度为n,经过m次二分查找到结果(即只剩下一个元素),则:n/(2^m) = 1(即n=m^2)。

其算法复杂度为o(log(n))

最大查找次数


二分查找因为每次都是从中间点开始查找,所以最大查找次数(最坏情况)是目标元素存在于最边缘的情况。比如1~9,最坏情况就是1或者9,当然4,6这种也算是边缘(中心的边缘)。

所以不难发现:
最多比较1次的串长是1
最多比较2次的串长是2-3
3是4-7
4是8-15
x是2^(x-1)-2^x-1

最坏情况下次数:logN+1(logN向下取整)

赞(1)
未经允许不得转载:爱上极客 » 二分查找的时间复杂度,最大查找次数
分享到: 更多 (0)

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    似花还似非花,也无人惜从教坠。
    抛家傍路,思量却是,无情有思。

    互传电商网4年前 (2015-07-18)回复