Python bisect模块
程序员文章站
2024-03-19 21:36:04
...
Python的bisect模块是内置模块,bisect模块实现了一个算法用于有序序列的插入和查找。。
在一些情况下,这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect是二分法的意思,这里使用二分法排序,将待插入的元素插入到合适的位置
bisect模块提供了如下几个函数:
(下面函数中的lo和hi用于指定列表的区间,默认的是整个列表)
- 查找: bisect(array, item)
bisect.bisect_left(a, x, lo=0, hi=len(a)) 返回将x插入到列表a中的索引位置,如果已有x,则返回第一个x的位置
bisect.bisect_right(a, x, lo=0, hi=len(a)) 返回将x插入到列表a中的索引位置,如果已有x,则返回最后一个x位置的下一个位置
bisect.bisect(a, x, lo=0, hi=len(a)) 与bisect_right相同
- 插入: insort(array,item)
bisect.insort_left(a, x, lo=0, hi=len(a)) 将x插入到列表a中,如果已有x,插入到所有x的最左边
bisect.insort_right(a, x, lo=0, hi=len(a)) 将x插入到列表a中,如果已有x,插入到所有x的最右边
bisect.insort(a, x, lo=0, hi=len(a)) 与insort_right相同
代码:
import bisect
a=[1,3,5,7,9,11]
index_l=bisect.bisect_left(a,3) # 查找目标元素左侧插入点
index_r=bisect.bisect_right(a,3) #查找目标元素右侧插入点
index=bisect.bisect(a,3) #同 bisect_right()
print("左侧索引:",index_l,"右侧索引:",index_r,"索引:",index)
index_l=bisect.bisect_left(a,4) # 查找目标元素左侧插入点
index_r=bisect.bisect_right(a,4) #查找目标元素右侧插入点
index=bisect.bisect(a,4) #同 bisect_right()
print("左侧索引:",index_l,"右侧索引:",index_r,"索引:",index)
输出:
左侧索引: 1 右侧索引: 2 索引: 2
左侧索引: 2 右侧索引: 2 索引: 2
上一篇: 二分查找递归与循环实现
下一篇: etcd raft cap 理解