bisect — Алгоритм деления массива пополам

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

Поиск в отсортированных списках

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

def index(a, x):
    'Ищет самое левое значение, точно равное x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Ищет самое правое значение меньше, чем x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Ищет самое правое значение, меньшее или равное x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Ищет крайнее левое значение больше, чем x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Ищет крайний левый элемент больше или равный 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, потому что это приведёт к неэффективному дизайну (последовательные вызовы функций деления пополам не будут «запоминать» все предыдущие поиски ключей).

Вместо этого лучше выполнить поиск в списке предварительно вычисленных ключей, чтобы найти индекс рассматриваемой записи:

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