bisect ---数组平分算法

源代码： Lib/bisect.py

---

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

提供以下功能：

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

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

返回的插入点 i 对阵列进行分区 a 分成两半，这样就可以 all(val < x for val in a[lo : i]) 对于左侧和 all(val >= x for val in a[i : hi]) 放在右边。

key 指定一个 key function 用于从每个输入元素提取比较关键字的一个参数的。默认值为 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() ，但返回一个插入点，该插入点位于 x 在里面 a .

返回的插入点 i 对阵列进行分区 a 分成两半，这样就可以 all(val <= x for val in a[lo : i]) 对于左侧和 all(val > x for val in a[i : hi]) 放在右边。

key 指定一个 key function 用于从每个输入元素提取比较关键字的一个参数的。默认值为 None (直接比较元素)。

在 3.10 版更改: 添加了 key 参数。

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

插入 x 在……里面 a 按排序的顺序。

key 指定一个 key function 用于从每个输入元素提取比较关键字的一个参数的。默认值为 None (直接比较元素)。

此函数首先运行 bisect_left() 若要定位插入点，请执行以下操作。接下来，它运行 insert() 方法打开 a 要插入 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 在里面 a 在任何现有条目之后 x .

key 指定一个 key function 用于从每个输入元素提取比较关键字的一个参数的。默认值为 None (直接比较元素)。

此函数首先运行 bisect_right() 若要定位插入点，请执行以下操作。接下来，它运行 insert() 方法打开 a 要插入 x 位于适当位置以维持排序顺序。

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

在 3.10 版更改: 添加了 key 参数。

绩效说明

编写时间敏感型代码时，请使用 平分() 和 insorte() ，请记住这些想法：

• 二分法对于搜索值范围是有效的。在查找特定值方面，字典的性能更好。

• 这个 insorte() 函数有 O(n) 因为对数搜索步长由线性时间插入步长控制。

• 搜索函数是无状态的，并在使用关键函数结果后将其丢弃。因此，如果在循环中使用搜索函数，则可以在相同的数组元素上一次又一次地调用键函数。如果键函数速度不快，可以考虑用 functools.cache() 以避免重复计算。或者，可以考虑搜索预计算键数组来定位插入点(如下面的示例部分所示)。

参见

• Sorted Collections 是一个高性能模块，它使用 平分 到托管的排序数据集合。

• 这个 SortedCollection recipe 使用二等分生成功能齐全的集合类，该集合类具有直接的搜索方法和对键函数的支持。预计算键以避免在搜索期间对键函数进行不必要的调用。

搜索排序列表

以上 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)