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

Примечания о производительности

При написании чувствительного ко времени кода с использованием bisect() и insort() учитывайте следующее:

• Бисекция эффективна для поиска в диапазонах значений. Для поиска конкретных значений производительнее использовать словари.
• Функции insort() имеют сложность O(n), поскольку логарифмический этап поиска уступает по скорости линейному этапу вставки.
• Функции поиска не хранят состояние и отбрасывают результаты функции-ключа после использования. Поэтому при вызове функций поиска в цикле функция-ключ может снова и снова вызываться для одних и тех же элементов массива. Если функция-ключ работает медленно, рассмотрите возможность обернуть её в @functools.cache, чтобы избежать повторных вычислений. Другой вариант — искать точку вставки в массиве заранее вычисленных ключей (как показано в примерах ниже).

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

Описанные выше функции 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):
...     i = bisect([60, 70, 80, 90], score)
...     return "FDCBA"[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

Функции bisect() и insort() также работают со списками кортежей. Аргумент key позволяет извлекать поле, по которому упорядочиваются записи в таблице:

>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint

>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

>>> movies = [
...     Movie('Jaws', 1975, 'Spielberg'),
...     Movie('Titanic', 1997, 'Cameron'),
...     Movie('The Birds', 1963, 'Hitchcock'),
...     Movie('Aliens', 1986, 'Cameron')
... ]

>>> # Find the first movie released after 1960
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')

>>> # Insert a movie while maintaining sort order
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
 Movie(name='Love Story', released=1970, director='Hiller'),
 Movie(name='Jaws', released=1975, director='Spielberg'),
 Movie(name='Aliens', released=1986, director='Cameron'),
 Movie(name='Titanic', released=1997, director='Cameron')]

Если функция-ключ работает медленно, повторных вызовов можно избежать, выполнив поиск в списке заранее вычисленных ключей, чтобы найти индекс записи:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Precompute a 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)