You are here:  Home » Python » bisect-数组二分算法详解(35)Python语言(必读进阶学习教程)(参考资料)

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

提供以下功能:

bisect.bisect_leftaxlo = 0hi = len(a)
a中找到x的插入点以维护排序顺序。参数lohi可用于指定应考虑的列表的子集; 默认情况下,使用整个列表。如果x已经存在于a中,则插入点将位于任何现有条目之前(左侧)。返回值适合用作假设a已经排序的第一个参数。list.insert()

返回的插入点i将阵列a分成两半,以便左侧和 右侧。all(val < x for val in a[lo:i])all(val >= x for valin a[i:hi])

bisect.bisect_rightaxlo = 0hi = len(a)
bisect.bisectaxlo = 0hi = len(a)
类似于bisect_left(),但返回一个插入点,该插入点位于ax的任何现有条目之后(右侧)。

返回的插入点i将阵列a分成两半,以便左侧和 右侧。all(val <= x for val in a[lo:i])all(val > x for valin a[i:hi])

bisect.insort_leftaxlo = 0hi = len(a)
插入X一个排序顺序。这相当于 假设a已经排序。请记住,O(log n)搜索由缓慢的O(n)插入步骤控制。a.insert(bisect.bisect_left(a, x, lo, hi), x)
bisect.insort_rightaxlo = 0hi = len(a)
bisect.insortaxlo = 0hi = len(a)
类似于insort_left(),但在任何现有条目之后插入x

也可以看看

SortedCollection配方使用bisect来构建具有直接搜索方法的全功能集合类并支持键功能。密钥是预先计算的,以便在搜索期间保存对键功能的不必要调用。

搜索排序列表

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

 

其他例子

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() 具有关键反向参数没有意义,因为这会导致设计效率低下(对二等分函数的连续调用不会“记住”所有先前的键查找)。

相反,最好搜索预先计算的键列表以查找相关记录的索引:

>>>

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