Python语言实现二分法查找
作者:五包辣条! 时间:2021-12-01 18:39:49
前言:
二分法也就是二分查找,它是一种效率较高的查找方法
假如公司新来了一个人,叫张三,他是你们公司第47个人,过了一段时间后,有些人呢看张三不爽,离职了,那这时候张三肯定不是公司第47个人了,怎么样才知道张三排第几呢,下面我们用二分法把他找出来
思路:
给你一本1000页的书籍,随机给定一个页码,如何用最快的方式找到它?如果一页一页逐步去查找,则最高需要查找一千次!那我们如何用二分法来解决这个问题呢?二分法的关键就是二分这个词。
步骤1:设定一个页码作为中心点来将1000页分为两份,中位数的作用就是每次缩小一半查找范围,即达到开方的效果。即可以用 (首位+末位)/2 = 中位数。
步骤2:将需要查找的页码与中位数比价,如果大于中位数则舍弃对中位数的前一半查找,反之则舍弃对后一半范围查找,达成开方效果。 步骤3:在新的查找范围重新计算出中位数
步骤4:查找页码对比中位数,确定新的查找范围
步骤5:循环以上步骤,直到找到该页码为止
代码:
通过以上思路解析,我们知道了二分法实行步骤,接下来就通过代码来实现步骤,首先是循环实现
#模拟页码
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#首位值
low = 0
#末位值
height = len(array)-1
#设定查找页码
findNum = 1
#循环查找
while True:
#获取中位数
mid = int((low+height)/2)
#打印中位数,查看循环次数
print(array[mid])
#如果中位数小于查找值,则锁定后半段
if array[mid] < findNum:
#重置低位数
low = mid + 1
#如果中位数大于查找值,则锁定前半段
elif array[mid] > findNum:
#重置高位值
height = mid - 1
#找到数字则打印该值下标,终止循环
elif array[mid]==findNum:
print('find it:',array[mid],' index:',mid)
break
除了上述方式外,也可以使用递归来实现,代码更加简洁
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#函数递归
#定义一个函数,给三个形参:低位值,高位值,查找值
def BinarySearch(low,height,findNum):
#计算出中位数
middle = (low+height)//2
#如果中位数小于查找值,则锁定后半段
if findNum >array[middle]:
#重置低位数
low = middle +1
#如果中位数大于查找值,则锁定前半段
elif findNum<array[middle]:
#重置高位值
height = middle - 1
else:
#找到该值并返回
return '该值下标为:%s,值为:%s'%(middle,array[middle])
#没有找到则调用自身继续查找
return BinarySearch(low,height,findNum)
print(BinarySearch(array[0],len(array)-1,19))
总结:
根据结果反馈,使用二分法常规Python检索用循环方式找数字21,他是排在11位,中位数查询3次,使用Python二分法检索递归方式先取查询数字的倍数,然后锁定前半段进行索引,索引的步骤耗时更少
来源:https://blog.csdn.net/AI19970205/article/details/123464424
标签:Python,二分法,查找
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
有序列表 li ol
2008-07-30 12:31:00
Python enumerate()计数器简化循环
2022-07-31 22:15:43
详解Python如何使用Netmiko进行文件传输
2021-06-20 19:49:17
![](https://img.aspxhome.com/file/2023/7/68337_0s.png)
oracle 日期函数
2010-07-23 13:32:00
获取mssql的xml返回结构的方法
2007-08-23 12:52:00
基于python解线性矩阵方程(numpy中的matrix类)
2023-11-03 06:54:12
Go语言转换所有字符串为大写或者小写的方法
2023-06-21 19:48:07
利用Opencv中Houghline方法实现直线检测
2023-09-07 12:40:39
![](https://img.aspxhome.com/file/2023/0/84000_0s.png)
asp随机生成文件名的函数
2009-02-11 13:41:00
Python采集C站热榜数据实战示例
2022-05-03 13:13:13
Python Pyecharts绘制桑基图分析用户行为路径
2022-06-07 02:47:57
![](https://img.aspxhome.com/file/2023/7/79527_0s.jpg)
Python使用sklearn实现的各种回归算法示例
2021-02-18 10:00:55
![](https://img.aspxhome.com/file/2023/9/80409_0s.png)
为什么首页最后设计
2009-07-17 19:03:00
该用多大的字
2009-05-17 14:39:00
ASP连接SQL2005数据库连接代码
2011-03-25 10:44:00
Asp无组件生成缩略图
2007-10-26 12:08:00
减少SQL Server死锁的方法
2009-01-05 13:49:00
MySQL数据库中对前端和后台进行系统优化
2009-01-04 13:39:00
详解用python生成随机数的几种方法
2022-01-24 14:17:42
Python中try excpet BaseException(异常处理捕获)的使用
2023-07-30 16:21:37
![](https://img.aspxhome.com/file/2023/0/71520_0s.png)