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.

См.также

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