bisect

bisect — Array bisection algorithm

2.1版本中的新功能。

源代码： Lib / bisect.py

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

提供以下功能：

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

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

返回的插入点我分隔阵列一个分为两半，使得all(val < x for val in a[lo:i])用于左侧和all(val >= x for val 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()，但返回其自带后（到右侧）的任何现有条目的插入点X在一个。

返回的插入点我分隔阵列一个分为两半，使得all(val <= x for val in a[lo:i])用于左侧和all(val > x for val in a[i:hi])用于右侧。

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

插入X在一个排序顺序。这相当于a.insert(bisect.bisect_left(a, x, lo, hi), 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 的任何现有条目之后的x中插入x。

1.搜索排序列表

上述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

2.其他例子

该bisect()函数可用于数字表查找。这个例子使用bisect()根据一组有序的数字断点来查找考试成绩（比如说）的字母等级：90和up是'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']

与sorted()函数不同，函数bisect()具有关键或颠倒的参数是没有意义的，因为这会导致设计效率低下（对等函数的连续调用不会“记住”所有先前的关键字查找）。

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

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