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

与`sorted()`函数不同的是，`bisect()`函数具有键或颠倒 t7 >因为这会导致设计效率低下（连续调用平分函数不会“记住”以前的所有键查找）。

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

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