【Python 百炼成钢】二分法查找
Python 查找 二分法
2023-09-27 14:20:14 时间
写在前面的话🪐
学了Python一些基础知识之后,相信大家对Python使用方法有了一定的感悟,想要追求深层次的东西还要细细的学、慢慢的学。Python基础教程更新到今天语法基础算是完了,本专栏后续会对面向对象模块更新。在进行面向对象更新之前呢会有一步小插曲就是Python 百炼成钢系列。主要的作用呢就是使用Python刷一刷算法题,使自己的基础更加稳固。在更新期间收到了广大小伙伴的喜爱,博主的知识水平也有所提升。下面呢咱们进入正题讲解今天咱们要学习的二分查找法。
问题描述🪐
在学习一门语言的时候,咱们做的最多的一件事就是对数据进行增删改查,而对于增删改查操作中最常做的就是查,因为一个软件主要的作用就是对亲爱的用户进行信息展示,只有少部分管理员或者拥有权限的用户才可以操作数据。比如在链表、数组中查找东西,咱们需要从头开始遍历,挨个检索。数据量庞大的时候会很令人头疼。今天介绍的二分法查找(或称折半查找) 主要是针对有序数列(也就是说数据要先排序)。然后每次取中值进行比较,依次折半缩小查找范围。
原理分析🪐
1.实现步骤
- 1)确定该区间的中间位置K,在数组两边加上区间左右边界l,r
- 2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。
区域确定如下:
- 每一次查找与中间值比较,判断是否查找成功,不成功当前查找区间将缩小一半。
视情况重新定左右边界与中间索引k- 时间复杂度为:O(log2n)。
2.图解
图片源于网络
参考代码🪐
这里在写代码的时候对比了系统内置查找关键字in与二分法查找的运行效果
打印结果如下:
由此可见Python底层的查找算法还是超级快的。使用起来也很方便
二分查找在本次实验中输在了需要对列表进行排序上
对于有序量大的数据就可以体现出来二分查找的优势了
import time,math,random
#计时器(使用的是函数装饰器前面说函数的时候提到过)
def timeT(func):
def wapper(*s):
start=time.perf_counter()
judge=func(*s)
end=time.perf_counter()
return judge,start-end
return wapper
# 使用内置查找方法
@timeT
def serch1(lists,e):
return e in lists
# 二分法
@ timeT
def serch2(lists,e):
flag=False
lists=sorted(lists)
# print(lists)
# 左游标
lo=0
# 右游标
ma=len(lists)-1
# 中间位置
mid=len(lists)//2
# 没有在列表内
if lists[ma]<e:
return False
if lists[lo]>e:
return False
# 依次缩小左右游标,直到lo>ma
while lo<=ma:
if lists[mid]>e:
ma=mid
mid=(lo+ma)//2
elif lists[mid]<e:
lo=mid
mid=(lo+ma)//2
else:
#标记位,True代表查到了
flag=True
break
return flag
def main():
#生成一个含有10000个元素的列表
numarr=[x for x in range(10000)]
#打乱列表顺序
random.shuffle(numarr)
print(*serch1(numarr,23))
print(*serch2(numarr,223))
print(223 in numarr)
# print(numarr)
if __name__=="__main__":
main()
相关文章
- 【华为OD机试真题 python】查找充电设备组合【2023 Q1 | 200分】
- 【华为OD机试真题 python】查找单入口空闲区域【2022 Q4 | 100分】
- Python 查找Twitter中特定话题中最流行的10个转发Tweet
- 也谈 Python 的中文编码处理
- python集合set用法详解(创建、增加、删除、复制、查找、合并、判断、差集、交集、对称差集)
- 华为python机试题目:查找兄弟单词、称砝码、单词倒排、购物单、合并表记录
- python split()函数
- 如何运用Python绘制NBA投篮图表
- python 根据目录查找指定文件
- 《树莓派Python编程入门与实战》——2.2 使用Raspbian命令行
- 用于查找子列表总和的 Python 程序
- 《Python数据可视化之matplotlib实践》 源码 第一篇 入门 第四章
- Python避坑指南(续)
- 【Python分布式服务框架】python实现gRPC服务
- 3、数组——二维数组中的查找(python版)
- 2022&2023华为OD机试 - 竖直四子棋(Python)
- 【Python】二维数组降序排序例子
- python 闭包
- 【Python数据结构】——二叉平衡树AVL(查找、构建、删除、插入、打印、遍历)
- [Python] split()方法