bisect --- 數組二分查找算法

源代碼： Lib/bisect.py

---

這個模塊對有序列表提供了支持，使得他們可以在插入新數據仍然保持有序。對于長列表，如果其包含元素的比較操作十分昂貴的話，這可以是對更常見方法的改進。這個模塊叫做 bisect 因為其使用了基本的二分（bisection）算法。源代碼也可以作為很棒的算法示例（邊界判斷也做好啦?。?/p>

定義了以下函數：

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

在 a 中找到 x 合適的插入點以維持有序。參數 lo 和 hi 可以被用于確定需要考慮的子集；默認情況下整個列表都會被使用。如果 x 已經在 a 里存在，那么插入點會在已存在元素之前（也就是左邊）。如果 a 是列表（list）的話，返回值是可以被放在 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]) for the right side。

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

將 x 插入到一個有序序列 a 里，并維持其有序。如果 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()，但是把 x 插入到 a 中已存在元素 x 的右側。

參見

SortedCollection recipe 使用 bisect 構造了一個功能完整的集合類，提供了直接的搜索方法和對用于搜索的 key 方法的支持。所有用于搜索的鍵都是預先計算的，以避免在搜索時對 key 方法的不必要調用。

搜索有序列表

上面的 bisect() 函數對于找到插入點是有用的，但在一般的搜索任務中可能會有點尷尬。下面 5 個函數展示了如何將其轉變成有序列表中的標準查找函數

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() 函數來說，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)