二分查找复杂度分析

二分查找有着查找速度快平均性能好等优点,但必须要求待查表为有序表,且插入删除困难 看看JDK二分查找源码中的实现

private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        
        /* 如果改为 low < high,就有可能出现本来数组中有待查元素,却查不到的情况
          比如查10,前两次查找和查12一样,最后low和high指向了元素10,
          但是此时while(low<high)不成立,所以会跳出循环    
         */
        while (low <= high) {
            int mid = (low + high) >>> 1;//使用位操作,效率高
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // 找到目标
        }
        return -(low + 1);  // 没找到目标.
    }

复杂度分析

你要查找的数据规模如果是n,那二分一次后规模就变为n/21,二分两次后规模为n/22,...,二分m次后规模为n/2^m,若二分m次后跳出循环,则m就是循环的次数(不管查找是否成功)

最坏情况(即查不到)

假设二分m次后剩下一个元素,那么此时规模为1,同时二分m次后规模变为n/2m,则:n/2m = 1, 解出 m = lg(n),此时再循环一次,查找不到,跳出循环,所以说最多有 m+1 次循环(二分m次未跳出循环,还要二分一次),也就是查找一个元素最多需要m+1次,即lg(n)+1次比较,故二分的最坏时间复杂度为O(n) = lg(n)

折半后,要对一半元素进行遍历,复杂度是O(n),所以算法的时间复杂度为O(n * lg(n))

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏顶级程序员

还有哪些类似0.99999…=1有趣的事实?

来自:几用来包的回答 - 知乎 链接:https://www.zhihu.com/question/37118994/answer/70677255(点击尾部...

38870
来自专栏顶级程序员

一位资深程序员大牛给予Java初学者的学习路线建议

Java学习这一部分其实也算是今天的重点,这一部分用来回答很多群里的朋友所问过的问题,那就是你是如何学习Java的,能不能给点建议?今天我是打算来点干货,因此...

435120
来自专栏顶级程序员

什么才算是真正的编程能力?

来源:知乎 链接:www.zhihu.com/question/31034164/ 小编注:本文综合整理自知乎同名问答帖。题主的问题补充如下: 还在读书,也在...

31460
来自专栏顶级程序员

治污女工程师走近垃圾写代码,监督2.5万家企业排污

转自:程序猿(imkuqin) 因为一段被偶然拍上网的路旁写代码视频,阿里云算法工程师佳米突然火了。 ? 因为经常和治污项目打交道,佳米当时并没有意识到正在垃...

36780
来自专栏顶级程序员

高斯模糊的算法

来自:阮一峰的网络日志 链接:www.ruanyifeng.com/blog/2012/11/gaussian_blur.html 通常,图像处理软件会提供"...

37490
来自专栏顶级程序员

王咏刚:为什么 AI 工程师都要懂些架构?

作者简介 王咏刚 Google软件工程师 著名技术撰稿人和IT演说家 创新工场AI工程院副院长 AI 时代,我们总说做科研的 AI 科学家、研究员、算法工程师...

39860
来自专栏醒者呆

算法精解:DAG有向无环图

DAG是公认的下一代区块链的标志。本文从算法基础去研究分析DAG算法,以及它是如何运用到区块链中,解决了当前区块链的哪些问题。 关键字:DAG,有向无环...

1.1K60
来自专栏顶级程序员

高并发系统限流中的漏桶算法和令牌桶算法,通过流量整形和速率限制提升稳定性

转自互联网金融小站(internet-sky) 已获作者授权,拒绝二次转载 在大数据量高并发访问时,经常会出现服务或接口面对暴涨的请求而不可用的情况,甚至引...

474100
来自专栏顶级程序员

AlphaGo之父:关于围棋,人类3000年来犯了一个错

转自澎湃新闻 “我会抱必胜心态、必死信念。我一定要击败阿尔法狗!” 对于5月23日至27日与围棋人工智能程序AlphaGo(阿尔法狗)的对弈,目前世界排名第一...

39970
来自专栏jojo的技术小屋

原 web安全、XSS、CSRF、注入攻击

作者:汪娇娇 时间:2017年8月15日 当时也是看了一本书《白帽子讲web安全》,简单的摘录然后做了个技术分享,文章不是很详细,建议大家结合着这本书看哈。 w...

58870

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励