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