位置: 编程技术 - 正文

Python实现二分查找与bisect模块详解(python 二分查找函数)

编辑:rootadmin

推荐整理分享Python实现二分查找与bisect模块详解(python 二分查找函数),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:python二分查找代码,python二分查找算法,python二分查找例题,python二分算法,python二分算法,python二分查找代码,python二分查找算法,python二分算法,内容如对您有帮助,希望把文章链接给更多的朋友!

前言

其实Python 的列表(list)内部实现是一个数组,也就是一个线性表。在列表中查找元素可以使用 list.index() 方法,其时间复杂度为O(n) 。对于大数据量,则可以用二分查找进行优化。

二分查找要求对象必须有序,其基本原理如下:

1.从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;

2.如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。

3.如果在某一步骤数组为空,则代表找不到。

二分查找也成为折半查找,算法每一次比较都使搜索范围缩小一半, 其时间复杂度为 O(logn)。

我们分别用递归和循环来实现二分查找:

接着对这两种实现进行一下性能测试:

执行结果如下:

可以看出循环方式比递归效率高。

bisect 模块

Python 有一个 bisect 模块,用于维护有序列表。bisect 模块实现了一个算法用于插入元素到有序列表。在一些情况下,这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思,这里使用二分法来排序,它会将一个元素插入到一个有序列表的合适位置,这使得不需要每次调用 sort 的方式维护有序列表。

下面是一个简单的使用示例:

输出结果:

Bisect模块提供的函数有:

bisect.bisect_left(a,x, lo=0, hi=len(a)) :

Python实现二分查找与bisect模块详解(python 二分查找函数)

查找在有序列表 a 中插入 x 的index。lo 和 hi 用于指定列表的区间,默认是使用整个列表。如果 x 已经存在,在其左边插入。返回值为 index。

bisect.bisect_right(a,x, lo=0, hi=len(a))

bisect.bisect(a, x,lo=0, hi=len(a)) :

这2个函数和 bisect_left 类似,但如果 x 已经存在,在其右边插入。

bisect.insort_left(a,x, lo=0, hi=len(a)) :

在有序列表 a 中插入 x。和 a.insert(bisect.bisect_left(a,x, lo, hi), x) 的效果相同。

bisect.insort_right(a,x, lo=0, hi=len(a))

bisect.insort(a, x,lo=0, hi=len(a)) :

和 insort_left 类似,但如果 x 已经存在,在其右边插入。

Bisect 模块提供的函数可以分两类: bisect* 只用于查找 index, 不进行实际的插入;而 insort* 则用于实际插入。

该模块比较典型的应用是计算分数等级:

执行结果:

同样,我们可以用 bisect 模块实现二分查找:

我们再来测试一下它与递归和循环实现的二分查找的性能:

可以看到其比循环实现略快,比递归实现差不多要快一半。

Python 著名的数据处理库 numpy 也有一个用于二分查找的函数 numpy.searchsorted, 用法与 bisect 基本相同,只不过如果要右边插入时,需要设置参数 side='right',例如:

那么,我们再来比较一下性能:

可以发现 numpy.searchsorted 效率是很低的,跟 bisect 根本不在一个数量级上。因此 searchsorted 不适合用于搜索普通的数组,但是它用来搜索 numpy.ndarray 是相当快的:

numpy.searchsorted 可以同时搜索多个值:

总结

标签: python 二分查找函数

本文链接地址:https://www.jiuchutong.com/biancheng/381383.html 转载请保留说明!

上一篇:python基础教程之五种数据类型详解(python基础教程视频教程)

下一篇:python递归删除指定目录及其所有内容的方法(pythonlist删除指定位置元素)

  • 税控盘抵扣税款
  • 一般纳税人外地预交税款怎么预缴
  • 收款和出库哪个借方哪个贷方?
  • 去年缴纳印花税忘记做账了怎么办呢
  • 企业入统的利弊
  • 社保基数是按税前工资还是税后工资
  • 个人提供劳务给个人,不开票要缴税吗
  • 提供劳务企业所得税纳税义务发生时间
  • 单位搬迁员工怎么办
  • 企业购买饮水机滤芯会计分录
  • 企业减免6%的税的营业范围有哪些?
  • 农产品普通发票抵扣怎么申报
  • 企业购进固定资产进项税如何抵扣
  • 股东借款作为资本金投入
  • 产品毛利率计算表
  • 汇算清缴时交的税怎么算
  • 交通费,通讯费均按照上级行标准领取
  • 未知文件格式怎么打开
  • 651错误是怎么回事
  • 签证费会计分录
  • 防伪税控开票系统技术维护费
  • uniapp微信小程序支付流程
  • 葛根泡水喝的七大功效
  • php字符串数组函数
  • 企业合作建房会计核算
  • 公司作为股东有什么好处
  • wamp设置
  • 稿酬所得计入什么科目
  • 外籍人员一次性奖金
  • 微前端架构实现
  • 小企业会计准则适用于哪些企业
  • 邮电费什么意思
  • 什么是Unicode
  • php投票系统代码
  • detr训练自己的数据集
  • 销售蔬菜企业怎么做
  • 三代手续费的税率
  • 包装物为什么是无菌的
  • 固定资产入账是税前还是税后
  • 收支平衡表excel怎么做
  • 普票红冲要不要去收回发票联?
  • 委托加工物资的成本包括
  • 医院如何开票
  • 转让不动产增值税征收管理办法
  • 电子承兑过期超过10天就无法转让吗
  • 未支付怎么取消
  • 年度汇算清缴缴税的会计分录
  • 餐饮企业老板
  • 营业外收入适用的会计准则
  • 客户用个人账户转4s店开公司的机动车发票
  • 固定资产有尾款怎么入账
  • 软件公司购买软件用于研发
  • 税务会计每个月几号需要干工作流程
  • 怎么设置现金流
  • MySQL利用不同的流程语句输出1到200的和
  • mysql的修改命令
  • win8系统怎么安装office
  • xp剪贴板怎么打开
  • 开机后cpu占用高
  • linux比较两个文件的差异
  • windows xp输入法不见了怎么办
  • windows8.1备份
  • mac文本软件
  • linux中软链接和硬链接的区别
  • linux命令的含义
  • linux 有哪些
  • linux如何使用vim编写程序
  • Windows下自动备份MongoDB的批处理脚本
  • 控制角色一致性的5个方法
  • mysql源码安装和二进制安装
  • pycharm怎么学
  • jquery开发项目
  • nodejs 写文件
  • javascript 继承
  • Rotate object with mouse click or touch in Unity3D
  • javascript 自动执行
  • android键盘aosp
  • 土地增值额未超过20%
  • 浙江增值税电子普通发票用支付宝怎么开
  • 江苏税务局电子
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设