python中的bisect模块与二分查找详情
1.bisect模块概述
bisect是python的内置模块, 用于有序序列的插入和查找。 插入的数据不会影响列表的排序, 但是原有列表需要是有序的, 并且不能是倒序.
Bisect模块提供的函数有:
- bisect.bisect_left(a,x, lo=0, hi=len(a))
- bisect.bisect_right(a,x, lo=0, hi=len(a))
- bisect.bisect(a, x,lo=0, hi=len(a))
- bisect.insort_left(a,x, lo=0, hi=len(a))
- bisect.insort_right(a,x, lo=0, hi=len(a))
- bisect.insort(a, x,lo=0, hi=len(a))
2.bisect模块的函数详解
2.1 bisect.bisect*()方法
- bisect.bisect_left(a,x,lo=0,hi=len(a),*,key=None)
在有序数组a中[lo,hi]区间内查找x插入的位置,返回的是索引值。如果a中有跟x相同的元素,则x插入的位置是左边,key指定了一个单参数的方法,该方法的返回值作为与k比较的基准。
值得注意的是,key参数是3.10版本以后才添加的功能
- bisect.bisect_right(a,x,lo=0,hi=len(a),*,key=None),在有序数组a中[lo,hi]区间内查找x插入的位置,返回索引值。如果a中有跟x相同的元素,则x插入的位置是右边。
- bisect.bisect(a,x,lo=0,hi=len(a),*,key=None),同bisect_right
# bisect_left Vs. bisect (bisect_right) import bisect nums = [1, 2, 2, 4] i, j = bisect.bisect_left(nums, 2), bisect.bisect(nums, 2) print(i) # 输出1 print(j) # 输出3
可见,针对上面给出的数组,想要插入2,使用bisect_left返回的索引值是1,使用bisect(bisect_right)返回的索引值是3。如果指定了lo和hi的话,那么返回的就是在这个范围内的索引。如下面的例子所示。
# 指定lo和hi import bisect nums = [1, 2, 2, 2, 2, 4] i = bisect.bisect_left(nums, 2, 3) print(i) # 输出为3
如果不指定lo=3的话,返回的索引应该是1。指定lo=3后,返回的索引为3。
关键字key指定了一个方法,这个方法会接受当前数组中的中间值mid(因为二分查找就是从中间值开始的)作为其参数,然后返回一个值val,val用于跟x比较。
# 指定key值 import bisect nums = [1, 2, 3, 4, 6, 8] def divide(mid): print('mid: ' + str(mid)) return mid // 2 i = bisect.bisect_left(nums, 5, key=divide) print(i)
上面的例子中定义了一个divide方法。那么bisect_left方法的执行顺序是这样的:
- nums中的中间值mid=4, divide(mid)方法返回值为2
- 5>2,则查找nums的右子数组,即[6,8]
- [6,8]的中间值是mid=8, divide(mid)方法返回值为4
- 5>4,则继续查找右子数组,可是已经没有右子数组了,则返回索引值为6.
2.2 bisect.insort*()方法
- bisect.insort_left(a,x,lo=0,hi=len(a),*,key=None),在有序数组a中[lo,hi]区间内查找x插入的位置,返回的是索引值。如果a中有跟x相同的元素,则x插入的位置是最左边,key指定了一个单参数的方法,该方法的返回值作为与k比较的基准。
- bisect.insort_right(a,x,lo=0,hi=len(a),*,key=None),在有序数组a中[lo,hi]区间内查找x插入的位置,返回索引值。如果a中有跟x相同的元素,则x插入的位置是最右边。
- bisect.insort(a,x,lo=0,hi=len(a),*,key=None),同insort_right。
# bisect.insort_left import bisect nums = [1, 2, 3, 4, 6, 8] bisect.insort_left(nums, 5) print(nums) # [1, 2, 3, 4, 5, 6, 8]
值得注意的是,insort方法中的key和bisect方法中的key指定的方法针对的对象是不同的。
# bisect.insort_left with key import bisect nums = [1, 2, 3, 4, 6, 8] def divide(mid): print('mid: ' + str(mid)) return mid // 2 bisect.insort_left(nums, 5, key=divide)
可见,key指定的方法的参数是针对x的。也就是说insort_left方法的执行顺序是这样的:
- mid=x=5,返回的值是2,也就是divide(x)
- mid是数组的中间值,即mid=4, divide方法返回的值是2
- divide(x)==2,则查找左子数组
- 中间值为2,mid=2, divide方法返回的值是1
- divide(x)>1,则查找右子数组
- 中间值为3,mid=3, divide方法的返回值是1
- divide(x)>1,则查找右子数组
- 没有右子数组了,则插入位置的索引为3,得到了插入5之后的数组为[1,2,3,5,4,6,8]
3.python中的二分查找
3.1 标准的二分查找
class BinarySearch: # 标准的二分查找,找不到返回-1 def binsearch(self, nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid elif nums[mid] > target: hi = mid - 1 else: # nums[mid] < target: lo = mid + 1 return -1
3.2 查找第一个>=target的元素索引
class BinarySearch: # 查找第一个>=target的元素索引,找不到返回数组长度 def lowerbound(self, nums, target): lo, hi = 0, len(nums) - 1 pos = len(nums) # 找不到 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] >= target: hi = mid else: # nums[mid] < target: lo = mid + 1 if nums[lo] >= target: # lo:要找的元素索引 pos = lo return pos
3.3 查找第一个>target的元素索引
class BinarySearch: # 查找第一个>target的元素索引,找不到返回数组长度 def upperbound(self, nums, target): lo, hi = 0, len(nums) - 1 pos = len(nums) # 找不到 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] > target: hi = mid else: # nums[mid] <= target: lo = mid + 1 if nums[lo] > target: # lo:要找的元素索引 pos = lo return pos
4.二分查找的变形与 bisect 模块的关系
- 二分查找中的
lowerbound(nums, target)
等价于bisect.bisect_left(a,x, lo=0, hi=len(a))
- 二分查找中的
upperbound(nums, target)
等价于bisect.bisect_right(a,x, lo=0, hi=len(a))
或者bisect.bisect(a,x, lo=0, hi=len(a))
到此这篇关于python中的bisect模块与二分查找详情的文章就介绍到这了,更多相关python bisect模块 内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/weixin_44852067/article/details/126815
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了PyTorch一小时掌握之迁移学习篇,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-08
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-25
- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要介绍了Python绘制的爱心树与表白代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-06