python二分法查找算法实现方法【递归与非递归】
作者:xlengji 发布时间:2023-04-17 08:13:47
标签:python,二分法查找,算法
本文实例讲述了python二分法查找算法实现方法。分享给大家供大家参考,具体如下:
二分法查找
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
二分法查找实现
(非递归实现)
def binary_search(alist, item):
first = 0
last = len(alist)-1
while first<=last:
midpoint = (first + last)/2
if alist[midpoint] == item:
return True
elif item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
(递归实现)
def binary_search(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return True
else:
if item<alist[midpoint]:
return binary_search(alist[:midpoint],item)
else:
return binary_search(alist[midpoint+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
运行结果:
False
True
时间复杂度
最优时间复杂度:O(1)
最坏时间复杂度:O(logn)
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/xlengji/article/details/82147639
0
投稿
猜你喜欢
- 问题原因:我遇到的情况,装了.NET2.0+IIS升级后就出现以上问题;不确定其他原因也会不会产生类似错误。(如果有,希望大家能贴出更多的原
- 由于存在函数内部不能访问全局作用的,所以就需要一种可以引入上一级作用域的语法结构,可以通过use使用函数声明时所在作用域的变量的值。php的
- 本文实例讲述了python在windows命令行下输出彩色文字的方法。分享给大家供大家参考。具体分析如下:默认情况下python在控制台输出
- 前言python使用中多线程、多进程、多协程使用是比较常见的。那么如果在多线程等的使用,我们这个时候我们想从外部强制杀掉该线程请问如何操作?
- 在matlab中,存在执行直接得函数来添加高斯噪声和椒盐噪声。Python-OpenCV中虽然不存在直接得函数,但是很容易使用相关的函数来实
- 由于Internet的历史原因,apin负责整个网络IP的整体规划以及北美区
- AJAX应用因为它们的表现力的丰富、更加互动和更加迅速的响应得到了赞扬声;这些优点都是通过使用XMLHttpRequest对象来动态的载入数
- * address - 地址 * blockquote - 块引用 * center - 举中对齐块 * di
- PHP+MySQL的组合是构建网站的一个常见搭配,不过如何使用PHP通过Web访问MySQL数据库呢?下面从Web数据库架构的工作原理讲起。
- CSS(叠层样式表)和XSL(可扩展样式语言)都可以定义XML文件的显示,这两种方式有哪些不同以及它们在使用中的具体方法,我们将在本文给予介
- 当“ 页面重构工程师 ”这个职位的面试官也蛮长一段时间了,跟前两年比起来,总的来说来应聘的同学能力在很大程度上有了提高,记得两年前的一场招聘
- Python 模块安装一. 打开命令提示符win + R 输入 cmd 点击确定或者win + S 搜索输入 cmd二. 环境变量没有问题的
- xml(可扩展标记语言)看起来可能像某种w3c标准——现在没有什么实际影响,即使以后能派上用场,也是很久以后的事。但实际上,它现在已经得到了
- 多表操作 在一个数据库中,可能存在多个表,这些表都是相互关联的。我
- Thinkphp6的日志问题日志级别debug, info, notice, warning, error, critical, alert
- --------------------------------------------------------- 正则收藏 手机号码: $
- 如何让用户也能修改密码? 好了,照下面添加到你要添加的地方去:<%id = Request(&qu
- 这段时间服务器崩溃2次,一直没有找到原因,今天看到论坛发出的错误信息邮件,想起可能是MySQL的默认连接数引起的问题,一查果然,老天,默认
- SQL Server 2000 清理日志精品教程SQL Server 2000 数据库日志太大!如何清理SQL Server 2000的日志
- 首先我们知道这个效果应该是一个老话题了。今天整理文件的时候,发现自己以前的一些布局的解决方法躺在文件夹里很长时间了,翻翻老底吧。需要说明的是