8.6. bisect - 数组对分算法

源代码： Lib / bisect.py

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

提供以下功能：

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

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

返回的插入点i将数组a分成两半，使得all（val x for val in a [lo：i]） 对于all（val > = x t15> in a [i：hi]）。

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(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.

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

以排序顺序在a中插入x。这相当于a.insert（bisect.bisect_left（a， x， lo， hi） t4> x），假设a已经排序。请记住，O（log n）搜索由缓慢的O（n）插入步骤控制。

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

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

也可以看看

SortedCollection食谱使用bisect通过直接搜索方法构建一个全功能的容器类，并支持键功能。密钥预先计算以在搜索期间节省对密钥功能的不必要的调用。

8.6.1.搜索排序列表

The above bisect() functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks.以下五个函数显示如何将它们转换为排序列表的标准查找：

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

8.6.2.其他示例

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

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).

相反，最好搜索预先计算的密钥列表以查找有问题的记录的索引：

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed 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)