Python算法练习之二分查找算法的实现
作者:小袁ITSuper 发布时间:2023-08-27 14:29:29
标签:Python,二分查找,算法
1. 算法描述
二分法是一种效率比较高的搜索方法
回忆之前做过的猜数字的小游戏,预先给定一个小于100的正整数x,让你猜猜测过程中给予大小判断的提示,问你怎样快速地猜出来?
我们之前做的游戏给定的是10次机会,如果我们学会.二分查找法以后,不管数字是多少,最多只需要7次就能猜到数字。
2. 算法分析
1、必须是有序的序列。
2、对数据量大小有要求。
数据量太小不适合二分查找,与直接遍历相比效率提升不明显。
数据量太大也不适合用二分查找,因为数组需要连续的存储空间,若数据量太大,往往找不到存储如此大规模数据的连续内存空间。.
3. 算法思路
假设有一个有序列表如下:
请问数字11是否在此列表中,如果在它的索引值为多少?
4. 代码实现
纯算法实现
实现代码
arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]
# 需要查找的数字
seek_number = 11
# 保存一共查找了几次
count = 0
# 列表左侧索引
left = 0
# 列表右侧索引
right = len(arr_list) - 1
# 当左侧索引小于等于右侧索引时
while left <= right:
# 取中间的索引位置
middle = (left + right) // 2
# 查找次数进行累加
count += 1
# 如果查找的数字大于中间位置的数字时
if seek_number > arr_list[middle]:
# 左侧索引为中间位置索引+1
left = middle + 1
# 如果查找的数字小于中间位置的数字时
elif seek_number < arr_list[middle]:
# 右侧索引为中间位置索引-1
right = middle - 1
# 如果等于中间索引数据
else:
print('数字:%s找到了,索引值为:%s' % (seek_number, middle))
break
else:
print("数字%s 没有找到" % seek_number)
print("一共用了:%s次查找" % count)
运行结果
递归法实现
在循环中定义了一个变量count,如果第一次循环后count没有变化,就说明输入的是有序序列,这时我们直接return退出循环,这时候的时间复杂度为O(n)
实现代码
arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]
def binary_search(seek_number, left, right):
if left <= right:
middle = (left + right) // 2
if seek_number < arr_list[middle]:
right = middle - 1
elif seek_number > arr_list[middle]:
left = middle + 1
else:
return middle
# 进行递归调用
return binary_search(seek_number, left, right)
# 当左侧索引大于右侧索引时,说明没有找到
else:
return -1
# 查找的数字
seek_number = 11
# 列表左侧索引
left = 0
# 列表右侧索引
right = len(arr_list) - 1
print("查找的数字:%s,索引为:%s" % (seek_number, binary_search(seek_number, left, right)))
运行结果
来源:https://blog.csdn.net/yuan2019035055/article/details/125301951
0
投稿
猜你喜欢
- python要知道怎么用好编译器。当我们编写Python代码时,我们得到的是一个包含Python代码的以.py为扩展名的文本文件。要运行代码
- 图像增强算子几何变换算子图像的几何变换又称为图像空间变换, 它将一幅图像中的坐标位置映射到另一幅图像中的新坐标位置。图像缩放缩放只是调整图像
- 本文实例讲述了PHP调用全国天气预报数据接口查询天气。分享给大家供大家参考,具体如下:基于PHP的聚合数据全国天气预报API服务请求的代码样
- FileSystemObject、Folder 和 File 对象的一些方法都与通过 TextStream 对象创建、读取或写入文件有关。虽
- 本文实例总结了Python实现string字符串连接的方法。分享给大家供大家参考,具体如下:以下基于python 2.7版本,代码片段真实有
- 本文实例讲述了pymongo实现控制mongodb中数字字段做加法的方法。分享给大家供大家参考。具体分析如下:这个非常实用,比如我们需要给文
- 工资excel表格格式如下所示:使用python批量给每位员工发送工资条信息,格式如下:思路:首先是加载excel,获取当前sheet表格s
- 代理服务是一种复杂的技术,具有很多可配置的移动组件。详细信息如下:信息信息是指在服务代理应用程序中调用的基本信息单元。对于服务代理来说,信息
- 每次抽取后都重新洗牌。计算10000次随机抽取可得到同花的几率。我做的比较复杂,分别累计了四种花色分别出现了几次import randoml
- 该sql如下:Select /*+ parallel(src, 8) */ distinct src.systemn
- 茎叶图from itertools import groupbynums2=[225, 232,232,245,235,245,270,22
- 以下内容是针对安装tensorflow-CPU版本的。tensorflow已经支持Python3.8版本的安装。可以查看自己的Python版
- 由于工作需要,在做最优分箱的时候,始终写不出来高效的代码,所以就找到了R语言中的最优分箱的包,这个时候考虑到了在python中调用R语言,完
- 1、引言小 * 丝:鱼哥, 都说要想代码写的溜,Lamdba不能少。小鱼:你在项目代码多写几个lamdba试试,看看架构师找不找你喝茶水。小 * 丝
- 自定义可迭代的类列表可以获取列表的长度,然后使用变量i对列表索引进行循环,也可以获取集合的所有元素,且容易理解。没错,使用列表的代码是容易理
- python2.7,下面是跑在window上的,稍作修改就可以跑在linux上。实测win7和raspbian均可,且raspbian可以直
- 在主图中背景颜色不知道怎么改,plt.plot()中没有axisbg参数。但是子图可以对plt.subplot的参数做修改,下面是对子图的背
- 新云4.0模版标签是全新改的了,加了前缀。如果你怀旧,请查看新云CMS3.1常用模板标签。下面的标签说明,后台就有,为了方便查看转到这里。{
- 本文实例讲述了Python 类方法和实例方法(@classmethod),静态方法(@staticmethod)。分享给大家供大家参考,具体
- 用法: 按住鼠标左键拖拽一个框后释放洗洗睡了<!DOCTYPE html public "-//W3C//DTD XHTML