8.5. bisect —数组二等分算法

2.1 版中的新Function。

源代码： Lib/bisect.py

---

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

提供以下Function：

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

返回的插入点* i 将数组 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()相似，但返回一个插入点，该插入点位于* a 中任何现有 x *条目之后(右侧)。

返回的插入点* i 将数组 a *分为两半，使得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)*)

  • 按排序 Sequences 在* a 中插入 x 。假设 a *已经排序，这等效于a.insert(bisect.bisect_left(a, x, lo, hi), x)。请记住，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()相似，但在* a 的任何现有条目之后，在 a 中插入 x *。

8.5.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

8.5.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()函数具有* key 或 reversed *参数是没有意义的，因为这将导致效率低下的设计(对 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)