8.5. bisect – алгоритм поиска вставки в массиве¶bisect – Array bisection algorithm

Исходный код: Lib/bisect.py

Этот модуль поддерживает хранение списка в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков, где операции сравнения дороги, это может быть эффективнее более распространенного подхода. Модуль называется bisect, потому что использует базовый алгоритм деления пополам. Исходный код может быть полезным как рабочий пример этого алгоритма (граничные условия уже правильные!).

Предоставляются следующие функции:

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

Находит точку вставки для x в a, чтобы сохранить сортировку. Параметры lo и hi можно использовать для указания подмножества списка; по умолчанию используется весь список. Если x уже присутствует в a, точка вставки будет перед (левее) всех существующих вхождений. Возвращаемое значение можно использовать в качестве первого аргумента для list.insert(), если a уже отсортирован.

Возвращаемая точка вставки 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(), но возвращает точку вставки, которая находится после (правее) всех существующих вхождений x в a.

Возвращаемая точка вставки 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))¶

Вставляет x в a в отсортированном порядке. Это эквивалентно a.insert(bisect.bisect_left(a, x, lo, hi), 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.

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

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

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # предварительно вычисленный список ключей
>>> 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)