【Python】详解 bisect 模块

目录

一、绪论

二、说明

2.1 bisect_left() 

2.2 bisect_right() 

2.3 bisect() 

2.4 insort_left()

2.5 insort_right()

2.6 insort()

2.7 知识延伸

一、绪论

想要使用二分搜索/二分查找但又懒得写肿么办？！当然是使用 bisect 模块 啦 ~~ 顾名思义，它是实现了 二分 (bisection) 算法 的模块，能够 保持序列 sequence 顺序不变 的情况下对其进行 二分查找和插入，适合用于降低对冗长序列查找的时间成本。当然，通过 “以空间换时间” 的方式也是可行的，例如用于构造 hashmap 的 Counter 类 (关于 Counter 模块详见 链接)。然而，本文的焦点是使用 bisect 模块 “凭查找方式降时间”，。

在 IDLE，通过调用内建函数 dir(bisect) 可查看 bisect 模块的属性和方法列表。可见，bisect 模块只有 6 个方法，相当简练。再调用 help(bisect) 则可以查看帮助文档。

>>> import bisect >>> dir(bisect) ['__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'bisect', 'bisect_left', 'bisect_right', 'insort', 'insort_left', 'insort_right']

其中的 6 个方法及其功能大致如下：

概括起来有些费解，但只要看完说明很容易就明白了 (鉴于网上各种资料是那么的糟心。。。)

注意，使用 bisect 模块的方法之前，须确保待操作对象是 有序序列，即元素已按 从大到小 / 从小到大 的顺序排列。

二、说明

2.1 bisect_left() 

bisect.bisect_left(a, x, [lo=0, hi=len(a)])：

在序列 a 中二分查找适合元素 x 插入的位置，保证 a 仍为 有序序列。

若序列 a 中存在与 x 相同的元素，则返回与 x 相同的第一个 (最左侧) 元素的位置索引，使得 x 若插入后能位于其 左侧；

若序列 a 中不存在与 x 相同的元素，则返回与 x 右侧距离最近的元素位置索引，使得 x 若插入后能位于其 左侧。

而 lo 和 hi 为可选参数，分别定义查找范围/返回索引的 上限和下限，缺省时默认对 整个 序列查找。

因此，返回的位置索引 又称为 “插入点”，将其设为 i，则序列 a 可以被划分为两部分，切片表示左侧 a[lo, i) 和右侧 a[i, hi] 。多说无益，观察一下测试内容吧：

 测试序列 a1 >>> a1 = [5, 6, 7, 8, 9] # 元素从小到大排列, 无重复, 等距 # lo 和 ho 缺省时默认查找整个序列 >>> bisect.bisect_left(a1, 4) # 与 x=4 右侧最近的元素是 5, 其位置 index=0 (若插入, list 变为 [4, 5, 6, 7, 8, 9]) 0 >>> bisect.bisect_left(a1, 4.5) # 与 x=4.5 右侧最近的元素是 5, 其位置 index=0 (若插入, list 变为 [4.5, 5, 6, 7, 8, 9]) 0 >>> bisect.bisect_left(a1, 5) # x=5 的位置 index=0 (若插入, list 变为 [5, 5, 6, 7, 8, 9]) 0 >>> bisect.bisect_left(a1, 5.5) # 与 x=5.5 右侧最近的元素是 6, 其位置 index=1 (若插入, list 变为 [5, 5.5, 6, 7, 8, 9]) 1 >>> bisect.bisect_left(a1, 6) # x=6 的位置 index=1 (若插入, list 变为 [5, 6, 6, 7, 8, 9]) 1 >>> bisect.bisect_left(a1, 6.5) # 与 x=6.5 右侧最近的元素是 7, 其位置 index=2 (若插入, list 变为 [5, 6, 6.5, 7, 8, 9]) 2 >>> bisect.bisect_left(a1, 7) # x=7 的位置 index=2 (若插入, list 变为 [5, 6, 7, 7, 8, 9]) 2 >>> bisect.bisect_left(a1, 7.5) # 与 x=7.5 右侧最近的元素是 8, 其位置 index=3 (若插入, list 变为 [5, 6, 7, 7.5, 8, 9]) 3 >>> bisect.bisect_left(a1, 8) # x=8 的位置 index=3 (若插入, list 变为 [5, 6, 7, 8, 8, 9]) 3 >>> bisect.bisect_left(a1, 8.5) # 与 x=8.5 右侧最近的元素是 9, 其位置 index=4 (若插入, list 变为 [5, 6, 7, 8, 8.5, 9]) 4 >>> bisect.bisect_left(a1, 9) # x=9 的位置 index=4 (若插入, list 变为 [5, 6, 7, 8, 9, 9]) 4 >>> bisect.bisect_left(a1, 9.5) # 默认上限 hi=5 (若插入, list 变为 [5, 6, 7, 8, 9, 9.5]) 5 >>> bisect.bisect_left(a1, 10) # 默认上限 hi=5 (若插入, list 变为 [5, 6, 7, 8, 9, 10]) 5

以上是理想情况，那不那么理想的情况呢？

 测试序列 a2 >>> a2 = [1, 3, 3, 4, 7] # 元素从小到大排列，有重复, 不等距 # lo 和 hi 缺省时默认查找整个序列 >>> bisect.bisect_left(a2, 0) # 与 x=0 右侧最近的元素是 1, 其位置 index=0 0 >>> bisect.bisect_left(a2, 0.5) # 与 x=0.5 右侧最近的元素是 1, 其位置 index=0 0 >>> bisect.bisect_left(a2, 1) # x=1 的位置 index=0 0 >>> bisect.bisect_left(a2, 1.5) # 与 x=1.5 右侧最近的元素是 3, 其位置 index=1 1 >>> bisect.bisect_left(a2, 2) # 与 x=2 右侧最近的元素是 3, 其位置 index=1 1 >>> bisect.bisect_left(a2, 2.5) # 与 x=2.5 右侧最近的元素是 3, 其位置 index=1 1 >>> bisect.bisect_left(a2, 3) # 第一个(最左侧) x=3 的位置 index=1 1 >>> bisect.bisect_left(a2, 3.5) # 与 x=3.5 右侧最近的元素是 4, 其位置 index=3 3 >>> bisect.bisect_left(a2, 4) # x=4 的位置 index=3 3 >>> bisect.bisect_left(a2, 4.5) # 与 x=4 右侧最近的元素是 7, 其位置 index=4 4 >>> bisect.bisect_left(a2, 5) # 与 x=5 右侧最近的元素是 7, 其位置 index=4 4 >>> bisect.bisect_left(a2, 5.5) # 与 x=5.5 右侧最近的元素是 7, 其位置 index=4 4 >>> bisect.bisect_left(a2, 6) # 与 x=6 右侧最近的元素是 7, 其位置 index=4 4 >>> bisect.bisect_left(a2, 6.5) # 与 x=6.5 右侧最近的元素是 7, 其位置 index=4 4 >>> bisect.bisect_left(a2, 7) # x=7 的位置 index=3 4 >>> bisect.bisect_left(a2, 7.5) # 默认上限 hi=5 5

那么再限制一下查找位置/返回索引/插入点的上下限呢？

 测试序列 a2 >>> a2 = [1, 3, 3, 4, 7] # 元素从小到大排列，有重复, 不等距 # 限定查找范围：[lo=1, hi=3] >>> bisect.bisect_left(a2, 0, 1, 3) # 与 x=0 右侧最近的元素是 1, 其位置 index=0, 但下限 lo=1, 故只能返回位置 index=1 1 >>> bisect.bisect_left(a2, 1, 1, 3) # x=1 的位置 index=0, 但下限 lo=1, 故只能返回位置 index=1 1 >>> bisect.bisect_left(a2, 2, 1, 3) # 与 x=2 右侧最近的元素是 3, 其位置 index=1 1 >>> bisect.bisect_left(a2, 3, 1, 3) # 第一个(最左侧) x=3 的位置 index=1 1 >>> bisect.bisect_left(a2, 4, 1, 3) # x=4 的位置 index=3 3 >>> bisect.bisect_left(a2, 5, 1, 3) # 与 x=5 右侧最近的元素是 7, 其位置 index=4, 但上限 hi=3, 故只能返回位置 index=3 3 >>> bisect.bisect_left(a2, 6, 1, 3) # 与 x=6 右侧最近的元素是 7, 其位置 index=4, 但上限 hi=3, 故只能返回位置 index=3 3 >>> bisect.bisect_left(a2, 7, 1, 3) # x=7 的位置 index=4, 但上限 hi=3, 故只能返回位置 index=3 3 >>> bisect.bisect_left(a2, 8, 1, 3) # 上限 hi=3 3

注意，Python 常用的 序列 sequence 除了 list，还有 string 和 tuple。tuple 类比于 list 还好理解，故仅简要展示一下 string：

 测试序列 a3 >>> a3 = 'acegi' # 元素从小到大排列，不重复, 等距 # 注意, 表明上看是按字母顺序, 实质上是按 ASCII 码顺序, 如 ord('a')=97, ord('b')=98 ... # lo 和 hi 缺省时默认查找整个序列 >>> bisect.bisect_left(a3, 'a') 0 >>> bisect.bisect_left(a3, 'b') 1 >>> bisect.bisect_left(a3, 'c') 1 >>> bisect.bisect_left(a3, 'd') 2 >>> bisect.bisect_left(a3, 'e') 2 >>> bisect.bisect_left(a3, 'f') 3 >>> bisect.bisect_left(a3, 'g') 3 >>> bisect.bisect_left(a3, 'h') 4 >>> bisect.bisect_left(a3, 'i') 4 >>> bisect.bisect_left(a3, 'j') 5

为什么要浓墨重彩地进行如此多的测试呢？那是因为该模块 只知其一，就知其二。

2.2 bisect_right() 

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

在序列 a 中二分查找适合元素 x 插入的位置，保证 a 仍为 有序序列。

若序列 a 中存在与 x 相同的元素，则返回与 x 相同的最后一个(最右侧)元素的位置索引，使得 x 若插入后能位于其 右侧；

若序列 a 中不存在与 x 相同的元素，则返回与 x 左侧距离最近的元素位置索引，使得 x 若插入后能位于其 右侧。

而 lo 和 hi 为可选参数，分别定义查找范围/返回索引的 上限和下限，缺省时默认对 整个 序列查找。

已知返回的位置索引为插入点 i，可将序列 a 划分为两部分：左侧 a[lo, i] 和右侧 a(i, hi] 。

 测试序列 a1 >>> a1 = [5, 6, 7, 8, 9] # 元素从小到大排列, 无重复, 等距 # lo 和 ho 缺省时默认查找整个序列 >>> bisect.bisect_right(a1, 4) # 下限 lo=0 0 >>> bisect.bisect_right(a1, 4.5) # 下限 lo=0 0 >>> bisect.bisect_right(a1, 5) # 与 x=5 左侧最近的元素是 5, 故插入点在 5 的后一位, 位置 index=0+1=1 (若插入, list 变为 [5, 5, 6, 7, 8, 9]) 1 >>> bisect.bisect_right(a1, 5.5) # 与 x=5.5 左侧最近的元素是 5, 故插入点在 5 的后一位, 位置 index=0+1=1 (若插入, list 变为 [5, 5.5, 6, 7, 8, 9]) 1 >>> bisect.bisect_right(a1, 6) # 与 x=6 左侧最近的元素是 6, 故插入点在 6 的后一位, 位置 index=1+1=2 (若插入, list 变为 [5, 6, 6, 7, 8, 9]) 2 >>> bisect.bisect_right(a1, 6.5) # 与 x=6.5 左侧最近的元素是 6, 故插入点在 6 的后一位, 位置 index=1+1=2 (若插入, list 变为 [5, 6, 6.5, 7, 8, 9]) 2 >>> bisect.bisect_right(a1, 7) # 与 x=7 左侧最近的元素是 7, 故插入点在 7 的后一位, 位置 index=2+1=3 (若插入, list 变为 [5, 6, 7, 7, 8, 9]) 3 >>> bisect.bisect_right(a1, 7.5) # 与 x=7.5 左侧最近的元素是 7, 故插入点在 7 的后一位, 位置 index=2+1=3 (若插入, list 变为 [5, 6, 7, 7.5, 8, 9]) 3 >>> bisect.bisect_right(a1, 8) # 与 x=8 左侧最近的元素是 8, 故插入点在 8 的后一位, 位置 index=3+1=4 (若插入, list 变为 [5, 6, 7, 8, 8, 9]) 4 >>> bisect.bisect_right(a1, 8.5) # 与 x=8.5 左侧最近的元素是 8, 故插入点在 8 的后一位, 位置 index=3+1=4 (若插入, list 变为 [5, 6, 7, 8, 8.5, 9]) 4 >>> bisect.bisect_right(a1, 9) # 与 x=9 左侧最近的元素是 9, 故插入点在 9 的后一位, 位置 index=4+1=5 (若插入, list 变为 [5, 6, 7, 8, 9, 9]) 5 >>> bisect.bisect_right(a1, 9.5) # 与 x=9.5 左侧最近的元素是 9, 故插入点在 9 的后一位, 位置 index=4+1=5 (若插入, list 变为 [5, 6, 7, 8, 9, 9.5]) 5 >>> bisect.bisect_right(a1, 10) # 与 x=10 左侧最近的元素是 9, 故插入点在 9 的后一位, 位置 index=4+1=5 (若插入, list 变为 [5, 6, 7, 8, 9, 10]) 5

注意与 bisect.bisect_left() 对比分析，于是不作赘述。

2.3 bisect() 

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

同 bisect.bisect_right()

2.4 insort_left()

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

如果说 bisect.bisect_left() 是为了在序列 a 中 查找 元素 x 的插入点 (左侧)，那么 bisect.insort_left() 就是在找到插入点的基础上，真正地将元素 x 插入序列 a，从而改变序列 a 同时保持元素顺序。例如：

>>> a11 = [5, 6, 7, 8, 9] >>> bisect.insort_left(a11, 4.5) >>> a11 [4.5, 5, 6, 7, 8, 9] >>> a12 = [5, 6, 7, 8, 9] >>> bisect.insort_left(a12, 5.5) >>> a12 [5, 5.5, 6, 7, 8, 9] >>> a13 = [5, 6, 7, 8, 9] >>> bisect.insort_left(a13, 6.5) >>> a13 [5, 6, 6.5, 7, 8, 9] >>> a14 = [5, 6, 7, 8, 9] >>> bisect.insort_left(a14, 7.5) >>> a14 [5, 6, 7, 7.5, 8, 9] >>> a15 = [5, 6, 7, 8, 9] >>> bisect.insort_left(a15, 8.5) >>> a15 [5, 6, 7, 8, 8.5, 9] >>> a16 = [5, 6, 7, 8, 9] >>> bisect.insort_left(a16, 9.5) >>> a16 [5, 6, 7, 8, 9, 9.5]

注意与 bisect.bisect_left() 对比分析。

2.5 insort_right()

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

如果说 bisect.bisect_right() 是为了在序列 a 中 查找 元素 x 的插入点 (右侧)，那么 bisect.insort_right() 就是在找到插入点的基础上，真正地将元素 x 插入序列 a，从而改变序列 a 同时保持元素顺序。例如：

>>> a11 = [5, 6, 7, 8, 9] >>> bisect.insort_right(a11, 4.5) >>> a11 [4.5, 5, 6, 7, 8, 9] >>> a12 = [5, 6, 7, 8, 9] >>> bisect.insort_right(a12, 5.5) >>> a12 [5, 5.5, 6, 7, 8, 9] >>> a13 = [5, 6, 7, 8, 9] >>> bisect.insort_right(a13, 6.5) >>> a13 [5, 6, 6.5, 7, 8, 9] >>> a14 = [5, 6, 7, 8, 9] >>> bisect.insort_right(a14, 7.5) >>> a14 [5, 6, 7, 7.5, 8, 9] >>> a15 = [5, 6, 7, 8, 9] >>> bisect.insort_right(a15, 8.5) >>> a15 [5, 6, 7, 8, 8.5, 9] >>> a16 = [5, 6, 7, 8, 9] >>> bisect.insort_right(a16, 9.5) >>> a16 [5, 6, 7, 8, 9, 9.5]

注意与 bisect.bisect_right() 对比分析。

注意到，2.5 和 2.6 的结果并未显式地体现区别，因为要保证插入元素后的序列仍然保序，插入位置是唯一的；若序列中存在相同的元素，即便插入位置不唯一 (左侧/右侧查找并插入)，最终体现的结果也是完全一致的。

2.6 insort()

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

同 bisect.insort_right()。

2.7 知识延伸

除了 对有序序列进行元素查找和插入，bisect 模块还能这样使用：

从一个给定的考试成绩集合里，通过一个有序数字表，查出其对应的字母等级：90 分及以上是 ‘A’，80 到 89 是 ‘B’，以此类推：

>>> from bisect import * >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'): ... i = bisect(breakpoints, score) ... return grades[i] ... >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] # 列表解析式 按成绩划分等级 ['F', 'A', 'C', 'C', 'B', 'A', 'A']

与 sorted() 函数不同，对 bisect() 函数而言，key 或 reversed 参数并无意义。因为这将导致设计效率低下 (连续调用 bisect 函数时，不会 “记住” 过去查找过的 key)。相反，最好去搜索预先计算好的 key 列表，再来查找相关记录的索引 index，例如：

>>> from bisect import * >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)] # 元组列表 >>> data.sort(key=lambda r: r[1]) # 按数字排序 >>> data [('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)] >>> keys = [r[1] for r in data] # 获取 key 列表 >>> keys [0, 1, 5, 8] >>> data[bisect_left(keys, 0)] # 根据 key 列表查找 index ('black', 0) >>> data[bisect_left(keys, 1)] ('blue', 1) >>> data[bisect_left(keys, 5)] ('red', 5) >>> data[bisect_left(keys, 8)] ('yellow', 8)

参考文献：

8.6. bisect — 数组二分查找算法 — Python 3.6.15 文档