使用Python实现二分法查找的示例
作者:WindMoon。 发布时间:2022-02-08 13:52:53
标签:Python,二分法,查找
关于二分法的定义我就不说了,CSDN很多大牛和前辈都已经阐述的很清楚了,直接上代码。
首先,先创建一个名称为 binary_search 的函数:传递两个参数,元素列表和要查找的值。
def binary_search(_list, value):
接下来,在函数内部定义所需的变量,二分法的关键在于从列表的中间向两侧查找(表述可能不严谨,大概这个意思),所以为了直观起见,定义 left,right, mid 三个变量,分别代表:列表的起始索引,结束索引和中间索引。
left = 0 # 列表的起始索引
right = len(_list) # 列表的结束索引
mid = int((left + right)/2) # 采用此方法,通过四舍五入刚好可以定位到列表的中间位置
接下来是实现二分查找的关键部分,先定义一个while循环,使得查找可以顺利进行,while函数内嵌套 if 分支语句实现条件判断,共有三种情况:
1. _list[mid] == value: 中间值恰好是我们需要查找的值,那么直接返回对应的索引就可以了。
2. _list[mid] > value: 要查找的值在mid的左侧,更新right 的值为mid,缩小查找范围。
3._list[mid] < value:要查找的值在mid的右侧,更新left 的值为mid,到 mid 右侧进行查找。
最后,对mid的值做一下更新,以便开始下一轮查找,同时采用 while-else语句针对没有查找到的情况进行判断,并给定一个返回值。
while left < right:
if _list[mid] == value:
return mid
elif _list[mid] > value:
right = mid
else:
left = mid
mid = int((right + left)/2)
else:
return -1
最后,完整代码,以及测试运行表现如下:
""" a demo realize binary search"""
def binary_search(_list, value):
left = 0 # 列表的起始索引
right = len(_list) # 列表的结束索引
mid = int((left + right)/2) # 采用此方法,通过四舍五入刚好可以定位到列表的中间位置
while left < right:
if _list[mid] == value:
return mid
elif _list[mid] > value:
right = mid
else:
left = mid
mid = int((right + left)/2)
else:
return -1
index = "the index of value in the list: {}"
print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))
运行结果:
没有要查找的值的情况:
来源:https://blog.csdn.net/weixin_62517099/article/details/124377169
0
投稿
猜你喜欢
- iframe的防插与强插(一)中介绍了“市面上”能见到的两种防御被第三方网站iframe的方法,以及相应的变态突破方法。貌似把“受害人”逼上
- 本文较为详细的分析了php单一入口应用程序。分享给大家供大家参考。具体如下:什么是单一入口应用程序?在解释什么是单一入口应用程序之前,我们先
- 这篇文章主要介绍了Python搭建HTTP服务过程图解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 登录与注册两个按钮似乎天生就应该是排在一起的,就像很多地方的“确定”与“取消”一样,甚至排在一起的意义远远强于后者。于是长期以来,用户们也形
- 今天发现一个使用python写的管理cisco设备的小框架tratto,可以用来批量执行命令。下载后主要有3个文件:Systems.py 定
- 本文实例讲述了django框架model orM使用字典作为参数,保存数据的方法。分享给大家供大家参考,具体如下:假设有一个字典,里面已经有
- python time.sleep()-睡眠线程还是进程?它会阻止线程。如果查看Python源代码中的Modules / timemodul
- 代码如下:<html> <head> &nb
- 本文实例讲述了php实现mysql事务处理的方法。分享给大家供大家参考。具体分析如下:要实现本功能的条件是环境 mysql 5.2 /php
- 可变参数顾名思义,函数的可变参数是传入的参数可以变化的,1个,2个到任意个。当然可以将这些 参数封装成一个 list 或者 tuple 传入
- table.rows集合中是cell对象 cell.innerHTML = "<td>123</td>&q
- 参考服务器安装的是Centos 系统。uwsgi是使用pip安装的。nginx是使用yum install nginx安装。python 2
- Python画图主要用到matplotlib这个库。Matplotlib 是一个 Python 的 2D绘图库,它以各种硬拷贝格式和跨平台的
- 在许多用SQL Server实现的新的企业系统设计中,系统设计师需要在给数据结构和管理应用程序逻辑的定位上做出具有关键性意义的决定。SQL
- 创建小程序全局函数1:在微信开发工具中增加一个JS文档, 放入全局全局函数代码说明1:全局函数只能放var定义的变量下,本例的var 变量为
- 作为一个Oracle数据库开发者或者DBA,在实际工作中经常会遇到这样的问题:试图对库表中的某一列或几列创建唯一索引时,系统提示ORA-01
- 如下所示:url = u'http://tieba.baidu.com/f?kw=权利的游戏&ie=utf-8&pn
- 具体代码和说明如下:upload.asp<form action=http://<%= Request.&n
- 最近在做一个游戏数据统计后台,最基础的功能是通过分析注册登录日志来展示用户数据。在公司内部测试,用户量很少,所以就没有发现什么性能问题。但是
- 一、介绍Django特点:具有完整的封装,开发者可以高效率的开发项目,Django将大部分的功能进行了封装,开发者只需要调用即可,如此,大大