Python bisect 管理已排序的序列

本文最后更新于:2022年8月10日 上午

bisect 模块包含两个主要函数,bisectinsort,两个函数都利用 二分查找算法来在有序序列中查找或插入元素。

bisect

bisect是 python 的内置模块,主要用来管理已经排序的数据。

bisect搜索

1
bisect(haystack, needle) 
  • 在 haystack(干草垛)里搜索 needle(针)的位置,该位置满足的条件是,把 needle 插入这个位置之后,haystack 还能保持升序。
1
2
3
4
5
6
7
8
import bisect
data = [33,45,67,98,124,555,1235]
data.sort()
index = bisect.bisect(data, 99)

-->
index
4
  • 也就是在说这个函数返回的位置前面的值,都小于或等于 needle 的值
  • 其中 haystack 必须是一个有序的序列。
1
2
3
4
5
6
7
8
# 乱序的数组会返回错误的信息
import bisect
data = [33,45,1234, 67,1234, 98,1234, 124,555,1235]
index = bisect.bisect(data, 99)

-->
index
6

bisect.insort 插入新元素

  • 当排序数组需要插入元素时,可以先用 bisect(haystack, needle) 查找位置 index,再用 haystack.insert(index, needle) 来插入新值。但你也可用 bisect.insort 来一步到位,并且后者的速度更快一些。
  • 排序很耗时,因此在得到一个有序序列之后,我们最好能够保持它的有 序。bisect.insort 就是为了这个而存在的,在实现时用的二分搜索的方式查找位置。
1
2
3
4
5
6
7
8
import bisect
data = [33,45,67,98,124,555,1235]
data.sort()
bisect.insort(data, 101)

-->
data
[33, 45, 67, 98, 101, 124, 555, 1235]

参考资料


Python bisect 管理已排序的序列
https://www.zywvvd.com/notes/coding/python/fluent-python/chapter-2/python-bisect/python-bisect/
作者
Yiwei Zhang
发布于
2022年5月25日
许可协议