文档章节

算法笔记整理-查找算法---二分查找

落叶刀
 落叶刀
发布于 2017/10/10 21:44
字数 280
阅读 0
收藏 0

二分查找算法;其输入是一个有序的元素列表,如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null。

fg:猜测在1-100中的一个数字。

傻找:一个一个的排查,最多需要N次。

二分查找:每次排除一半的数据。第一次猜50,比大小后,再猜中间的数字以此类推成对数关系。最多需要log2n次。log以(2)为底(2的n次方)的对数化简为log2(100)=10。

(大O表示法:讨论运行时间时log指的都是log2。)

简单查找,在最糟糕的情况要N次,二次查找在最糟糕情况logn次。

 

© 著作权归作者所有

共有 人打赏支持
落叶刀
粉丝 41
博文 126
码字总数 107596
作品 2
浦东
运维
私信 提问
《算法图解》笔记(1) 二分查找

二分查找 二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回 null 。 一般而言,对于包含n个元素的列表,用二分查找最多需要l...

WMXNLFD
03/05
0
0
每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述,就是任何实现某种功能的代码片...

爱吃西瓜的番茄酱
2018/01/07
0
0
算法知识梳理(8) - 二分查找算法及其变型

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/12
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际...

dqcfkyqdxym3f8rb0
2017/11/24
0
0
算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

深入 理解char * ,char ** ,char a[ ] ,char *a[] 的区别

C语言中由于指针的灵活性,导致指针能代替数组使用,或者混合使用,这些导致了许多指针和数组的迷惑,因此,刻意再次深入探究了指针和数组这玩意儿,其他类型的数组比较简单,容易混淆的是字...

天王盖地虎626
23分钟前
1
0
关于我这三年的架构历程(待完成)

从16年7月实习至今,快三年的开发经历中,经手了好几个项目。目前有幸作为一个项目的负责人,完成了一个项目的完全架构设计。因此想记录下这份架构设计中的点点面面。 总架构: 基于DNS的负载...

赵熠熠
24分钟前
0
0
springboot 使用 flyway 进行数据库版本管理

要在启动时自动运行Flyway数据库迁移,请将其添加 org.flywaydb:flyway-core到类路径中。 迁移是表单中的脚本V<VERSION>__<NAME>.sql(使用<VERSION>下划线分隔的版本,例如“1”或“2_1”)...

NotFound403
43分钟前
4
0
spring 5.1.5版本(二)

spring 5.1.5版本(一) spring 5.1.5版本(二) spring 5.1.5版本(三) 对象创建方式 方式一 applicationContext.xml <?xml version='1.0' encoding='UTF-8'?><beans xmlns="http://ww......

gwl_
45分钟前
0
0
CMake生成Mingw用的Make文件

CMake 在win下 默认会生成vc++的nmake用的make 当没安装时 就会报 -- Building for: NMake Makefiles -- The C compiler identification is unknown -- The CXX compiler identification is......

shzwork
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部