Документация Python неофициальный перевод
Содержание страницы

8.5. bisect – Алгоритм бисекции массиваbisect – Array bisection algorithm

Этот модуль позволяет поддерживать список в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков элементов с дорогостоящими операциями сравнения такой подход может быть эффективнее более распространённых. Модуль называется 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.

См. также

Рецепт SortedCollection, использующий bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой ключевой функции. Ключи предварительно вычисляются, чтобы избежать лишних вызовов ключевой функции во время поиска.

8.5.1. Поиск в отсортированных спискахSearching Sorted Lists

Вышеупомянутые функции 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

8.5.2. Другие примерыOther Examples

Функция 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]         # предварительно вычисленный список ключей
>>> 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)