Python bisect 管理已排序的序列

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

bisect

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

bisect搜索

bisect(haystack, needle) 

• 在 haystack（干草垛）里搜索 needle（针）的位置，该位置满足的条件是，把 needle 插入这个位置之后，haystack 还能保持升序。

import bisect
data = [33,45,67,98,124,555,1235]
data.sort()
index = bisect.bisect(data, 99)

-->
index
4

• 也就是在说这个函数返回的位置前面的值，都小于或等于 needle 的值。
• 其中 haystack 必须是一个有序的序列。

# 乱序的数组会返回错误的信息
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 就是为了这个而存在的，在实现时用的二分搜索的方式查找位置。

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(2017年人民邮电出版社出版)

文章链接：
https://www.zywvvd.com/notes/coding/python/fluent-python/chapter-2/python-bisect/python-bisect/