25. bisect

bisect 模块用于维护有序列表，核心思想是采用二分法来进行搜索和插入。

25.1. 函数

>>> import bisect
>>> dir(bisect)
['__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'bisect', 'bisect_left', 'bisect_right', 'insort', 'insort_left', 'insort_right']
bisect_left(a, x, lo=0, hi=len(a))

返回 x 的插入位置，如果 a 中已经存在 x ，则返回最左侧 x 的位置。设该位置为 i ，则 all(val < x for val in a[lo:i]), all(val >= x for val in a[i:hi]) 。

bisect_right(a, x, lo=0, hi=len(a))

返回 x 的插入位置，如果 a 中已经存在 x ，则返回最右侧 x 的下一个位置。设该位置为 i ，则 all(val <= x for val in a[lo:i]), all(val > x for val in a[i:hi]) 。

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

同 bisect_right 。

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

等效于 a.insert(bisect.bisect_left(a, x, lo, hi), x) 。

insort_right(a, x, lo=0, hi=len(a))

等效于 a.insert(bisect.bisect_right(a, x, lo, hi), x) 。

insort(a, x, lo=0, hi=len(a))

同 insort_right 。

25.2. 搜索有序表

 1def index(a, x):
 2    'Locate the leftmost value exactly equal to x'
 3    i = bisect_left(a, x)
 4    if i != len(a) and a[i] == x:
 5        return i
 6    raise ValueError
 7
 8def find_lt(a, x):
 9    'Find rightmost value less than x'
10    i = bisect_left(a, x)
11    if i:
12        return a[i-1]
13    raise ValueError
14
15def find_le(a, x):
16    'Find rightmost value less than or equal to x'
17    i = bisect_right(a, x)
18    if i:
19        return a[i-1]
20    raise ValueError
21
22def find_gt(a, x):
23    'Find leftmost value greater than x'
24    i = bisect_right(a, x)
25    if i != len(a):
26        return a[i]
27    raise ValueError
28
29def find_ge(a, x):
30    'Find leftmost item greater than or equal to x'
31    i = bisect_left(a, x)
32    if i != len(a):
33        return a[i]
34    raise ValueError

25.3. 示例

1>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
2...     i = bisect(breakpoints, score)
3...     return grades[i]
4...
5>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
6['F', 'A', 'C', 'C', 'B', 'A', 'A']

25.4. 附：源码

 1"""Bisection algorithms."""
 2
 3def insort_right(a, x, lo=0, hi=None):
 4    """Insert item x in list a, and keep it sorted assuming a is sorted.
 5    If x is already in a, insert it to the right of the rightmost x.
 6    Optional args lo (default 0) and hi (default len(a)) bound the
 7    slice of a to be searched.
 8    """
 9
10    lo = bisect_right(a, x, lo, hi)
11    a.insert(lo, x)
12
13def bisect_right(a, x, lo=0, hi=None):
14    """Return the index where to insert item x in list a, assuming a is sorted.
15    The return value i is such that all e in a[:i] have e <= x, and all e in
16    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
17    insert just after the rightmost x already there.
18    Optional args lo (default 0) and hi (default len(a)) bound the
19    slice of a to be searched.
20    """
21
22    if lo < 0:
23        raise ValueError('lo must be non-negative')
24    if hi is None:
25        hi = len(a)
26    while lo < hi:
27        mid = (lo+hi)//2
28        if x < a[mid]: hi = mid
29        else: lo = mid+1
30    return lo
31
32def insort_left(a, x, lo=0, hi=None):
33    """Insert item x in list a, and keep it sorted assuming a is sorted.
34    If x is already in a, insert it to the left of the leftmost x.
35    Optional args lo (default 0) and hi (default len(a)) bound the
36    slice of a to be searched.
37    """
38
39    lo = bisect_left(a, x, lo, hi)
40    a.insert(lo, x)
41
42
43def bisect_left(a, x, lo=0, hi=None):
44    """Return the index where to insert item x in list a, assuming a is sorted.
45    The return value i is such that all e in a[:i] have e < x, and all e in
46    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
47    insert just before the leftmost x already there.
48    Optional args lo (default 0) and hi (default len(a)) bound the
49    slice of a to be searched.
50    """
51
52    if lo < 0:
53        raise ValueError('lo must be non-negative')
54    if hi is None:
55        hi = len(a)
56    while lo < hi:
57        mid = (lo+hi)//2
58        if a[mid] < x: lo = mid+1
59        else: hi = mid
60    return lo
61
62# Overwrite above definitions with a fast C implementation
63try:
64    from _bisect import *
65except ImportError:
66    pass
67
68# Create aliases
69bisect = bisect_right
70insort = insort_right

25.5. 参考资料

  1. bisect — Array bisection algorithm

  1. Python 的 bisect 模块