正文
【算法】二分查找法&大O表示法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
二分查找
基本概念
- 二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
- 使用二分查找时，每次都排除一半的数字
- 对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。
- 示例：
如果列表包含8个数字，你最多需要检查8个数字。
而使用二分查找时，最多需要检查log n个元素。如果列表包含8个元素，你最多需要检查3个元素，因为log 8 = 3（ 23 = 8）。
注意：仅当列表是有序的时候，二分查找才管用
- 数组：将一系列元素存储在一系列相邻的桶（bucket），即数组。数组从0开始编号：位置依次分别为#0，#1….
python算法
def binary_search(l,item):
low=0
high=len(l)-1
while low<=high:
mid=(low+high)//2
guess=l[mid]
if guess==item:
return mid
if guess>item:
high=mid-1
else:
low=mid+1
return Nonemy_list=[1,3,5,7,9]
print(binary_search(my_list,3))
print(binary_search(my_list,-3))运行结果：
1
None
运行时间
- 一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。
- 最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
- 二分查找的运行时间为对数时间（或log时间）
- 示例：
列表包含100个数字，简单查找最多需要猜100次。二分查找最多需要7次
O(n)：线性时间
O(log n)：对数时间
大O表示法
大O表示法是一种特殊的表示法，指出了算法的速度有多快
算法的运行时间以不同的速度增加
- 二分查找和简单查找的运行时间的增速不同
- 示例：
元素个数 | 简单查找 | 二分法查找 |
100个元素 | 100ms | 7ms |
10000个元素 | 10s | 14ms |
1000000000个元素 | 11day | 32ms |
随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。
因此，随着列表的增长，二分查找的速度比简单查找快得多。
- 大O表示法用处：仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。
- 大O表示法是为了能够比较操作数，它指出了算法运行时间的增速。
如：假设列表包含n个元素，
简单查找：需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。无单位。
二分查找：需要执行log n次操作。使用大O表示法，这个运行时间为O(log n)
- 大O表示法格式：O(n)，n为操作数
- 大 O 表示法指出了最糟情况下的运行时间
常见的大O运行时间
- 5种大O运行时间
O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法
PS：
- 算法的速度指的并非时间，而是操作数的增速。
- 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示。
- O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
阶乘时间
阶乘时间：需要执行n!（n的阶乘）次操作才能计算出结果，运行时间为O(n!)
小结- 二分查找的速度比简单查找快得多。
- O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其增速的角度度量的。
- 算法运行时间用大O表示法表示。
【算法】二分查找法&大O表示法的更多相关文章- 二分查找法&;大O表示法
二分查找法的输入是一个有序的元素列表,如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null Python代码(来源于<算法图解>一书): def binary_search( ...
- Java-数据结构与算法-二分查找法
1.二分查找法思路:不断缩小范围,直到low <= high 2.代码: package Test; import java.util.Arrays; public class BinarySe ...
- 白话算法：时间复杂度和大O表示法
转自:https://www.jianshu.com/p/59d09b9cee58 每一个优秀的开发者脑中都有时间概念.他们想给用户更多的时间让用户做他们想做的事情.他们通过最小化时间复杂度来实现这一 ...
- 算法时间复杂度、空间复杂度(大O表示法)
什么是算法? 计算机是人的大脑的延伸,它的存在主要是为了帮助我们解决问题. 而算法在计算机领域中就是为了解决问题而指定的一系列简单的指令集合.不同的算法需要不同的资源,例如:执行时间或消耗内存. 如果 ...
- 南理第八届校赛同步赛-F sequence//贪心算法&;二分查找优化
题目大意:求一个序列中不严格单调递增的子序列的最小数目(子序列之间没有交叉). 这题证明贪心法可行的时候,可以发现和求最长递减子序列的长度是同一个方法,只是思考的角度不同,具体证明并不是很清楚,这里就 ...
- #C++初学记录（贪心算法#二分查找）
D - Aggressive cows 农夫 John 建造了一座很长的畜栏,它包括N (2 <= N <= 100,000)个隔间,这些小隔间依次编号为x1,...,xN (0 < ...
- Java算法 -- 二分查找
折半查找,要求待查找的序列有序.每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程.直到 ...
- 莫队算法/二分查找 FZU 2072 Count
题目传送门 题意:问区间内x的出现的次数分析:莫队算法:用一个cnt记录x的次数就可以了.还有二分查找的方法 代码: #include <cstdio> #include <algo ...
- 查找算法----二分查找与hash查找
二分查找 有序列表对于我们的实现搜索是很有用的.在顺序查找中,当我们与第一个元素进行比较时,如果第一个元素不是我们要查找的,则最多还有 n-1 个元素需要进行比较. 二分查找则是从中间元素开始,而不是 ...
随机推荐- Mysql的主从数据库没有同步的解决办法
Mysql的主从数据库没有同步的解决办法 今天发现Mysql的主从数据库没有同步 先上Master库: mysql>show processlist; 查看下进程是否Sleep太多.发现很正常. ...
- 几种解析xml方式的比较
1: DOM DOM 是用与平台和语言无关的方式表示 XML 文档的官方 W3C 标准.DOM 是以层次结构组织的节点或信息片断的集合.这个层次结构允许开发人员在树中寻找特定信息.分析该结构通常需要加 ...
- 三个PHP常用代码样例
作为一个正常的程序员,会好几种语言是十分正常的,相信大部分程序员也都会编写几句PHP程序,如果是WEB程序员,PHP一定是必备的.尽管PHP经常被人诟病,被人贬低,被人当玩笑开,事实证明,PHP是全世 ...
- Django学习笔记（精简版）
dos:安装:python setup.py install 环境变量:D:\Python27;D:\Python27\Lib\site-packages\django\bin; 转到创建的目录:dj ...
- perl $d = encode_utf8($r); $f = decode_json($d)
[root@dr-mysql01 ~]# cat a1.pl my $url="http://192.168.32.101:3000/api/getcode?env=zj&phone ...
- 通过Log4net来配置我们需要的日志文件格式
我们先来看看配置写入txt文件是如何 的,当然不止可以配置txt格式还有其它格式. <?xml version="1.0" encoding="utf-8&qu ...
- .net自定义错误页面实现升级篇
问题描述: 在上一篇博文 ".net自定义错误页面实现" 中已经介绍了在.net中如何实现自定义错误页面实现(有需要者可以去上一篇博文了解),单纯按照上一篇博文那样设置,能够实现所 ...
- 2-Twelfth Scrum Meeting20151212
任务安排 成员 今日完成 明日任务 闫昊 获取视频播放的进度 获取视频播放进度 唐彬 解决handler可能引起的内存泄露问题 阅读IOS代码+阅读上届网络核心代码 史烨轩 下载service开发 ...
- UNIX高级环境编程（3）Files And Directories - stat函数，文件类型，和各种ID
在前面的两篇,我们了解了IO操作的一些基本操作函数,包括open.read和write. 在本篇我们来学习一下文件系统的其他特性和一个文件的属性,涉及的函数功能包括: 查看文件的所有属性: 改变文件所 ...
- 牛客国庆集训派对Day2 Solution
A 矩阵乘法 思路: 1° 牛客机器太快了,暴力能过. #include <bits/stdc++.h> using namespace std; #define N 5000 in ...
- 二分查找法&;大O表示法
二分查找法的输入是一个有序的元素列表,如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null Python代码(来源于<算法图解>一书): def binary_search( ...
- Java-数据结构与算法-二分查找法
1.二分查找法思路:不断缩小范围,直到low <= high 2.代码: package Test; import java.util.Arrays; public class BinarySe ...
- 白话算法：时间复杂度和大O表示法
转自:https://www.jianshu.com/p/59d09b9cee58 每一个优秀的开发者脑中都有时间概念.他们想给用户更多的时间让用户做他们想做的事情.他们通过最小化时间复杂度来实现这一 ...
- 算法时间复杂度、空间复杂度(大O表示法)
什么是算法? 计算机是人的大脑的延伸,它的存在主要是为了帮助我们解决问题. 而算法在计算机领域中就是为了解决问题而指定的一系列简单的指令集合.不同的算法需要不同的资源,例如:执行时间或消耗内存. 如果 ...
- 南理第八届校赛同步赛-F sequence//贪心算法&;二分查找优化
题目大意:求一个序列中不严格单调递增的子序列的最小数目(子序列之间没有交叉). 这题证明贪心法可行的时候,可以发现和求最长递减子序列的长度是同一个方法,只是思考的角度不同,具体证明并不是很清楚,这里就 ...
- #C++初学记录（贪心算法#二分查找）
D - Aggressive cows 农夫 John 建造了一座很长的畜栏,它包括N (2 <= N <= 100,000)个隔间,这些小隔间依次编号为x1,...,xN (0 < ...
- Java算法 -- 二分查找
折半查找,要求待查找的序列有序.每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程.直到 ...
- 莫队算法/二分查找 FZU 2072 Count
题目传送门 题意:问区间内x的出现的次数分析:莫队算法:用一个cnt记录x的次数就可以了.还有二分查找的方法 代码: #include <cstdio> #include <algo ...
- 查找算法----二分查找与hash查找
二分查找 有序列表对于我们的实现搜索是很有用的.在顺序查找中,当我们与第一个元素进行比较时,如果第一个元素不是我们要查找的,则最多还有 n-1 个元素需要进行比较. 二分查找则是从中间元素开始,而不是 ...
随机推荐- Mysql的主从数据库没有同步的解决办法
Mysql的主从数据库没有同步的解决办法 今天发现Mysql的主从数据库没有同步 先上Master库: mysql>show processlist; 查看下进程是否Sleep太多.发现很正常. ...
- 几种解析xml方式的比较
1: DOM DOM 是用与平台和语言无关的方式表示 XML 文档的官方 W3C 标准.DOM 是以层次结构组织的节点或信息片断的集合.这个层次结构允许开发人员在树中寻找特定信息.分析该结构通常需要加 ...
- 三个PHP常用代码样例
作为一个正常的程序员,会好几种语言是十分正常的,相信大部分程序员也都会编写几句PHP程序,如果是WEB程序员,PHP一定是必备的.尽管PHP经常被人诟病,被人贬低,被人当玩笑开,事实证明,PHP是全世 ...
- Django学习笔记（精简版）
dos:安装:python setup.py install 环境变量:D:\Python27;D:\Python27\Lib\site-packages\django\bin; 转到创建的目录:dj ...
- perl $d = encode_utf8($r); $f = decode_json($d)
[root@dr-mysql01 ~]# cat a1.pl my $url="http://192.168.32.101:3000/api/getcode?env=zj&phone ...
- 通过Log4net来配置我们需要的日志文件格式
我们先来看看配置写入txt文件是如何 的,当然不止可以配置txt格式还有其它格式. <?xml version="1.0" encoding="utf-8&qu ...
- .net自定义错误页面实现升级篇
问题描述: 在上一篇博文 ".net自定义错误页面实现" 中已经介绍了在.net中如何实现自定义错误页面实现(有需要者可以去上一篇博文了解),单纯按照上一篇博文那样设置,能够实现所 ...
- 2-Twelfth Scrum Meeting20151212
任务安排 成员 今日完成 明日任务 闫昊 获取视频播放的进度 获取视频播放进度 唐彬 解决handler可能引起的内存泄露问题 阅读IOS代码+阅读上届网络核心代码 史烨轩 下载service开发 ...
- UNIX高级环境编程（3）Files And Directories - stat函数，文件类型，和各种ID
在前面的两篇,我们了解了IO操作的一些基本操作函数,包括open.read和write. 在本篇我们来学习一下文件系统的其他特性和一个文件的属性,涉及的函数功能包括: 查看文件的所有属性: 改变文件所 ...
- 牛客国庆集训派对Day2 Solution
A 矩阵乘法 思路: 1° 牛客机器太快了,暴力能过. #include <bits/stdc++.h> using namespace std; #define N 5000 in ...
Mysql的主从数据库没有同步的解决办法 今天发现Mysql的主从数据库没有同步 先上Master库: mysql>show processlist; 查看下进程是否Sleep太多.发现很正常. ...
1: DOM DOM 是用与平台和语言无关的方式表示 XML 文档的官方 W3C 标准.DOM 是以层次结构组织的节点或信息片断的集合.这个层次结构允许开发人员在树中寻找特定信息.分析该结构通常需要加 ...
作为一个正常的程序员,会好几种语言是十分正常的,相信大部分程序员也都会编写几句PHP程序,如果是WEB程序员,PHP一定是必备的.尽管PHP经常被人诟病,被人贬低,被人当玩笑开,事实证明,PHP是全世 ...
dos:安装:python setup.py install 环境变量:D:\Python27;D:\Python27\Lib\site-packages\django\bin; 转到创建的目录:dj ...
[root@dr-mysql01 ~]# cat a1.pl my $url="http://192.168.32.101:3000/api/getcode?env=zj&phone ...
我们先来看看配置写入txt文件是如何 的,当然不止可以配置txt格式还有其它格式. <?xml version="1.0" encoding="utf-8&qu ...
问题描述: 在上一篇博文 ".net自定义错误页面实现" 中已经介绍了在.net中如何实现自定义错误页面实现(有需要者可以去上一篇博文了解),单纯按照上一篇博文那样设置,能够实现所 ...
任务安排 成员 今日完成 明日任务 闫昊 获取视频播放的进度 获取视频播放进度 唐彬 解决handler可能引起的内存泄露问题 阅读IOS代码+阅读上届网络核心代码 史烨轩 下载service开发 ...
在前面的两篇,我们了解了IO操作的一些基本操作函数,包括open.read和write. 在本篇我们来学习一下文件系统的其他特性和一个文件的属性,涉及的函数功能包括: 查看文件的所有属性: 改变文件所 ...
A 矩阵乘法 思路: 1° 牛客机器太快了,暴力能过. #include <bits/stdc++.h> using namespace std; #define N 5000 in ...
