bisect — Алгоритм бисекции массива

Исходный код: 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.

См. также

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

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

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

Другие примеры

Функция 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)