bisect — 数组二分算法

源代码： :source:`Lib/bisect.py`

该模块支持按排序顺序维护列表，而不必在每次插入后对列表进行排序。对于具有昂贵比较操作的长项目列表，这可能是对更常见方法的改进。该模块称为 bisect，因为它使用基本的二分算法来完成其工作。源代码作为算法的工作示例可能是最有用的（边界条件已经正确！）。

提供以下功能：

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

在 a 中找到 x 的插入点以保持排序顺序。参数 lo 和 hi 可用于指定应考虑的列表子集；默认使用整个列表。如果 x 已存在于 a 中，则插入点将位于任何现有条目之前（左侧）。假设 a 已经排序，返回值适合用作 list.insert() 的第一个参数。

返回的插入点 i 将数组 a 分成两半，以便左侧为 all(val < x for val in a[lo : i])，右侧为 all(val >= x for val in a[i : hi])。

key 指定一个参数的 key 函数，用于从每个输入元素中提取比较键。默认值为 None（直接比较元素）。

3.10 版更改：增加了 key 参数。

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None) bisect.bisect(a, x, lo=0, hi=len(a))

类似于 bisect_left()，但返回一个插入点，该插入点位于 a 中 x 的任何现有条目之后（右侧）。

返回的插入点 i 将数组 a 分成两半，以便左侧为 all(val <= x for val in a[lo : i])，右侧为 all(val > x for val in a[i : hi])。

key 指定一个参数的 key 函数，用于从每个输入元素中提取比较键。默认值为 None（直接比较元素）。

3.10 版更改：增加了 key 参数。

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

按排序顺序将 x 插入 a。

key 指定一个参数的 key 函数，用于从每个输入元素中提取比较键。默认值为 None（直接比较元素）。

该函数首先运行 bisect_left() 来定位插入点。接下来，它在 a 上运行 insert() 方法以在适当的位置插入 x 以保持排序顺序。

请记住，O(log n) 搜索由缓慢的 O(n) 插入步骤主导。

3.10 版更改：增加了 key 参数。

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None) bisect.insort(a, x, lo=0, hi=len(a))

类似于 insort_left()，但在 x 的任何现有条目之后插入 x 到 a。

key 指定一个参数的 key 函数，用于从每个输入元素中提取比较键。默认值为 None（直接比较元素）。

该函数首先运行 bisect_right() 来定位插入点。接下来，它在 a 上运行 insert() 方法以在适当的位置插入 x 以保持排序顺序。

请记住，O(log n) 搜索由缓慢的 O(n) 插入步骤主导。

3.10 版更改：增加了 key 参数。

性能说明

使用 bisect() 和 insort() 编写时间敏感代码时，请记住以下想法：

二分法对于搜索值范围很有效。对于定位特定值，字典的性能更高。
insort() 函数是 O(n)，因为对数搜索步骤由线性时间插入步骤主导。
搜索函数是无状态的，使用后丢弃关键函数结果。因此，如果在循环中使用搜索函数，则键函数可能会在相同的数组元素上一次又一次地被调用。如果关键函数不快，请考虑用 functools.cache() 包装它以避免重复计算。或者，考虑搜索一组预先计算好的键来定位插入点（如下面的示例部分所示）。

也可以看看

Sorted Collections 是一个高性能模块，它使用 bisect 来管理数据的排序集合。
SortedCollection recipe 使用 bisect 构建一个功能齐全的集合类，具有直接的搜索方法和对键函数的支持。这些键是预先计算好的，以便在搜索过程中保存对键功能的不必要调用。

搜索排序列表

上面的 bisect() 函数对于查找插入点很有用，但用于常见的搜索任务可能会很棘手或笨拙。以下五个函数显示了如何将它们转换为排序列表的标准查找：

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

例子

bisect() 函数可用于数值表查找。此示例使用 bisect() 根据一组有序的数字断点查找考试分数的字母等级（例如）：90 及以上是“A”，80 到 89 是“B” '，等等：

>>> 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']

避免重复调用键函数的一种技术是搜索预先计算的键列表以查找记录的索引：

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Precompute a list of keys.
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

bisect — 数组二分算法 — Python 文档

目录

bisect — 数组二分算法

性能说明

搜索排序列表

例子