【Python】详解 bisect 模块_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 文档