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

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

При написании кода, чувствительного к времени, с использованием bisect() и insort(), помните об этом:

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

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

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

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']

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