bisect — Array bisection algorithm数组对分算法

Source code: Lib/bisect.py

---

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. 此模块支持按排序顺序维护列表，而无需在每次插入后对列表进行排序。For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. 对于具有昂贵比较操作的长项目列表，这可能是对更常见方法的改进。The module is called bisect because it uses a basic bisection algorithm to do its work. 该模块称为bisect，因为它使用基本的对分算法来完成其工作。The source code may be most useful as a working example of the algorithm (the boundary conditions are already right!).作为算法的工作示例，源代码可能最有用（边界条件已经正确！）。

The following functions are provided:提供以下功能：

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

Locate the insertion point for x in a to maintain sorted order. 在a中定位x的插入点，以保持排序顺序。The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. 参数lo和hi可用于指定应考虑的列表子集；默认情况下，使用整个列表。If x is already present in a, the insertion point will be before (to the left of) any existing entries. 如果x已经存在于a中，则插入点将位于任何现有条目之前（左侧）。The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.假设已对a排序，则返回值适合用作list.insert()的第一个参数。

The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo : i]) for the left side and all(val >= x for val in a[i : hi]) for the right side.返回的插入点i将阵列a分成两半，以便all(val < x for val in a[lo : i])用于左侧，all(val >= x for val in a[i : hi])用于右侧。

key specifies a key function of one argument that is used to extract a comparison key from each input element. key指定一个参数的键函数，用于从每个输入元素中提取比较键。The default value is None (compare the elements directly).默认值为None（直接比较元素）。

Changed in version 3.10:版本3.10中更改： Added the key parameter.添加了key参数。

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

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

Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.类似于bisect_left()，但返回一个插入点，该插入点位于a中x的任何现有条目之后（右侧）。

The returned insertion point i partitions the array a into two halves so that all(val <= x for val in a[lo : i]) for the left side and all(val > x for val in a[i : hi]) for the right side.返回的插入点i将阵列a分成两半，以便all(val <= x for val in a[lo : i])用于左侧，all(val > x for val in a[i : hi])用于右侧。

key specifies a key function of one argument that is used to extract a comparison key from each input element. key指定一个参数的键函数，用于从每个输入元素中提取比较键。The default value is None (compare the elements directly).默认值为None（直接比较元素）。

Changed in version 3.10:版本3.10中更改： Added the key parameter.添加了key参数。

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

Insert x in a in sorted order.按排序顺序在a中插入x。

key specifies a key function of one argument that is used to extract a comparison key from each input element. key指定一个参数的键函数，用于从每个输入元素中提取比较键。The default value is None (compare the elements directly).默认值为None（直接比较元素）。

This function first runs bisect_left() to locate an insertion point. 此函数首先运行bisect_left()来定位插入点。Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.接下来，它在上运行insert()方法，在a的适当的位置插入x以保持排序顺序。

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.请记住，O(log n)搜索由缓慢的O(n)插入步骤控制。

Changed in version 3.10:版本3.10中更改： Added the key parameter.添加了key参数。

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

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

Similar to insort_left(), but inserting x in a after any existing entries of x.类似于insort_left()，但在a中的任何现有x项之后插入x。

key specifies a key function of one argument that is used to extract a comparison key from each input element. key指定一个参数的键函数，用于从每个输入元素中提取比较键。The default value is None (compare the elements directly).默认值为None（直接比较元素）。

This function first runs bisect_right() to locate an insertion point. 此函数首先运行bisect_right()来定位插入点。Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.接下来，它在上运行insert()方法，在a的适当的位置插入x以保持排序顺序。

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.请记住，O(log n)搜索由缓慢的O(n)插入步骤控制。

Changed in version 3.10:版本3.10中更改： Added the key parameter.添加了key参数。

Performance Notes性能说明

When writing time sensitive code using bisect() and insort(), keep these thoughts in mind:当使用bisect()和insort()编写对时间敏感的代码时，请记住以下想法：

• Bisection is effective for searching ranges of values. 二分法对于搜索值的范围是有效的。For locating specific values, dictionaries are more performant.对于定位特定值，字典更具性能。

• The insort() functions are O(n) because the logarithmic search step is dominated by the linear time insertion step.insort()函数是O(n)，因为对数搜索步骤由线性时间插入步骤控制。

• The search functions are stateless and discard key function results after they are used. 搜索函数是无状态的，使用后会丢弃关键函数结果。Consequently, if the search functions are used in a loop, the key function may be called again and again on the same array elements. 因此，如果在循环中使用搜索函数，则可以在相同的数组元素上反复调用键函数。If the key function isn’t fast, consider wrapping it with functools.cache() to avoid duplicate computations. 如果键函数速度不快，请考虑使用functools.cache()将其包装，以避免重复计算。Alternatively, consider searching an array of precomputed keys to locate the insertion point (as shown in the examples section below).或者，考虑搜索一组预计算键来定位插入点（如下面的示例部分所示）。

See also另请参见

• Sorted Collections已排序的集合 is a high performance module that uses bisect to managed sorted collections of data.是一个高性能模块，使用对分来管理已排序的数据集合。

• The SortedCollection recipe uses bisect to build a full-featured collection class with straight-forward search methods and support for a key-function. SortedCollection配方使用对分来构建一个功能齐全的集合类，该类具有直接的搜索方法并支持一个关键函数。The keys are precomputed to save unnecessary calls to the key function during searches.预计算键以节省搜索期间对键函数的不必要调用。

Searching Sorted Lists搜索排序列表

The above bisect() functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks. 上面的bisect()函数对于查找插入点很有用，但用于常见的搜索任务可能会很棘手或尴尬。The following five functions show how to transform them into the standard lookups for sorted lists:以下五个函数显示了如何将它们转换为排序列表的标准查找：

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

Examples示例

The bisect() function can be useful for numeric table lookups. bisect()函数的作用是查找数值表。This example uses bisect() to look up a letter grade for an exam score (say) based on a set of ordered numeric breakpoints: 90 and up is an ‘A’, 80 to 89 is a ‘B’, and so on:本例使用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']

One technique to avoid repeated calls to a key function is to search a list of precomputed keys to find the index of a record:避免重复调用键函数的一种技术是搜索预计算键列表以查找记录的索引：

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