Python真题案例之二分法查找详解
作者:酷尔。 发布时间:2023-09-23 01:39:07
写在前面的话🪐
学了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()
来源:https://blog.csdn.net/apple_51931783/article/details/123208914
猜你喜欢
- 代码如下:CREATE TABLE [dbo].[TbGuidTable]( [TableName] [varchar](50) NOT N
- 星爷的一部“国产007”应该是无人不晓,其中一个片段是将“007”向MM展示他的秘密武器。皮鞋可以吹头发,大哥大可以刮胡子……把真实功能隐蔽
- 和网友们讨论了数组取交集的方法,下面是两个实现arr1=["1","5","6"
- 1.1 闭包1、闭包概念1. 在一个外函数中定义了一个内函数,内函数里运用了外函数的临时变量,并且外函数的返回值是内函数的引用,这样就构成了
- 锟拷码和口字码说到乱码问题就不得不提到锟斤拷,这算是非常常见的一种乱码形式,那么它到底是经过何种错误操作产生的呢?下面我们一步步探究。看一个
- 14个超酷的js显示时间效果,一定有你想要的。正常时间显示运行效果图:<title>正常显示的时钟 - asp之家 - http
- 淘宝招聘的一个css题目:css样式控制div水平垂直居中方法;<!DOCTYPE html PUBLIC "-//W3C/
- 简介使用百度深度学习框架paddlepaddle对人像图片进行自动化抠图安装根据PaddlePaddle官网命令安装如pip install
- 在处理数据的时候,因为没有及时的去重,所以需要重新对生成txt进行去重。可是一个文件夹下有很多txt,总不可能一个一个去操作,这样效率太低了
- 今天我们来写一个有管理功能的留言板程序。所谓的管理功能,其实就是每条留言前有一个选择框,点中要删除的留言,或者点“删除所有留言”,就完成了批
- 有时候需要在网页中某个div载入之后,动态引入一段javascript,IE下的解决方案: newjs. onreadystatechang
- 这个是作者自己封装的一个钉钉机器人的包,目前只支持发文本格式、链接格式、markdown格式的消息,我们可以在很多场景用到这个,比如告警通知
- Oracle的分析函数功能非常强大,工作这些年来经常用到。这次将平时经常使用到的分析函数整理出来,以备日后查看。我们拿案例来学习,这样理解起
- Python版本 实现了比之前的xxftp更多更完善的功能1、继续支持多用户2、继续支持虚拟目录3、增加支持用户根目录以及映射虚拟目录的权限
- 有一台windows服务器上跑着mysql的一些应用,现在需要将mysql的数据每天备份,并通过ftp上传到指定的存储服务器上要是在linu
- 在DOS界面运行python的py文件我用的Notepad++编写代码,编写完后需要在DOS界面运行打开DOS界面按键盘上的WIN+R,输入
- ASP从发布至今已经7年了,使用ASP技术已经相当成熟,自从微软推出了ASP.NET之后就逐渐停止了对ASP版本的更新。但是由于有很多人仍然
- 本文实例讲述了php下pdo的mysql事务处理用法。分享给大家供大家参考。具体分析如下:php+mysql事务处理的几个步骤:1.关闭自动
- 本文实例讲述了python中尾递归用法。分享给大家供大家参考。具体分析如下:如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递
- //获取元素的样式值。 function getStyle(elem,name){ if(elem.style[name]){ return