bisect.md

1> **Источник:** https://python-all.ru/3.10/library/bisect.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# [`bisect`](https://python-all.ru/3.10/library/bisect.html#module-bisect) – алгоритм деления массива пополам89**Исходный код:** [Lib/bisect.py](https://python-all.ru/src/3.10/Lib/bisect.py)1011---1213Этот модуль поддерживает хранение списка в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков, где операции сравнения дороги, это может быть эффективнее более распространенного подхода. Модуль называется [`bisect`](https://python-all.ru/3.10/library/bisect.html#module-bisect), потому что использует базовый алгоритм деления пополам. Исходный код может быть полезным как рабочий пример этого алгоритма (граничные условия уже правильные!).1415Предоставляются следующие функции:1617#### `bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)`1819Находит точку вставки для *x* в *a*, чтобы сохранить сортировку. Параметры *lo* и *hi* можно использовать для указания подмножества списка; по умолчанию используется весь список. Если *x* уже присутствует в *a*, точка вставки будет перед (левее) всех существующих вхождений. Возвращаемое значение можно использовать в качестве первого аргумента для `list.insert()`, если *a* уже отсортирован.2021Возвращаемая точка вставки *i* делит массив *a* на две половины так, что для левой части выполняется `all(val < x for val in a[lo : i])`, а для правой – `all(val >= x for val in a[i : hi])`.2223*key* задаёт [функцию ключа](https://python-all.ru/3.10/glossary.html#term-key-function) с одним аргументом, которая извлекает ключ сравнения из каждого элемента массива. Для поддержки поиска в сложных записях функция ключа не применяется к значению *x*.2425Если *key* равен `None`, элементы сравниваются напрямую, без вызова промежуточной функции.2627Изменено в версии 3.10: Добавлен параметр *key*.2829#### `bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)`3031#### `bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)`3233Аналогично [`bisect_left()`](https://python-all.ru/3.10/library/bisect.html#bisect.bisect_left), но возвращает точку вставки, которая находится после (правее) всех существующих вхождений *x* в *a*.3435Возвращаемая точка вставки *i* делит массив *a* на две половины так, что для левой части выполняется `all(val <= x for val in a[lo : i])`, а для правой – `all(val > x for val in a[i : hi])`.3637*key* задаёт [функцию ключа](https://python-all.ru/3.10/glossary.html#term-key-function) с одним аргументом, которая извлекает ключ сравнения из каждого элемента массива. Для поддержки поиска в сложных записях функция ключа не применяется к значению *x*.3839Если *key* равен `None`, элементы сравниваются напрямую, без вызова промежуточной функции.4041Изменено в версии 3.10: Добавлен параметр *key*.4243#### `bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)`4445Вставляет *x* в *a* в отсортированном порядке.4647Сначала эта функция запускает [`bisect_left()`](https://python-all.ru/3.10/library/bisect.html#bisect.bisect_left) для поиска точки вставки. Затем она вызывает метод `insert()` у *a*, чтобы вставить *x* в нужное место для сохранения порядка сортировки.4849Чтобы поддерживать вставку записей в таблицу, функция *key* (если задана) применяется к *x* на этапе поиска, но не на этапе вставки.5051Имейте в виду, что `O(log n)` поиск в основном определяется медленным O(n) шагом вставки.5253Изменено в версии 3.10: Добавлен параметр *key*.5455#### `bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)`5657#### `bisect.insort(a, x, lo=0, hi=len(a), *, key=None)`5859Аналогично [`insort_left()`](https://python-all.ru/3.10/library/bisect.html#bisect.insort_left), но вставляет *x* в *a* после всех существующих вхождений *x*.6061Сначала эта функция запускает [`bisect_right()`](https://python-all.ru/3.10/library/bisect.html#bisect.bisect_right) для поиска точки вставки. Затем она вызывает метод `insert()` у *a*, чтобы вставить *x* в нужное место для сохранения порядка сортировки.6263Чтобы поддерживать вставку записей в таблицу, функция *key* (если задана) применяется к *x* на этапе поиска, но не на этапе вставки.6465Имейте в виду, что `O(log n)` поиск в основном определяется медленным O(n) шагом вставки.6667Изменено в версии 3.10: Добавлен параметр *key*.6869## Примечания по производительности7071При написании кода, чувствительного ко времени, с использованием *bisect()* и *insort()*, учитывайте следующее:7273- Бинарный поиск эффективен для поиска в диапазонах значений. Для поиска конкретных значений словари более производительны.74- Функции *insort()* являются `O(n)`, поскольку логарифмический шаг поиска перекрывается линейным шагом вставки.75- Функции поиска не имеют состояния и отбрасывают результаты ключевой функции после их использования. Следовательно, если функции поиска используются в цикле, ключевая функция может вызываться снова и снова для одних и тех же элементов массива. Если ключевая функция не быстрая, рассмотрите обёртку с помощью [`functools.cache()`](https://python-all.ru/3.10/library/functools.html#functools.cache), чтобы избежать повторных вычислений. В качестве альтернативы рассмотрите поиск по массиву предварительно вычисленных ключей для определения точки вставки (как показано в разделе примеров ниже).7677> **См. также**78>79> - [Sorted Collections](https://python-all.ru/3.10/library/bisect.html) – это высокопроизводительный модуль, использующий *bisect* для управления отсортированными коллекциями данных.80> - Рецепт [SortedCollection](https://python-all.ru/3.10/library/bisect.html) использует bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой ключевой функции. Ключи предварительно вычисляются, чтобы избежать лишних вызовов ключевой функции во время поиска.8182## Поиск в отсортированных списках8384Вышеупомянутые функции [`bisect()`](https://python-all.ru/3.10/library/bisect.html#module-bisect) полезны для поиска точек вставки, но могут быть неудобны или сложны для обычных задач поиска. Следующие пять функций показывают, как преобразовать их в стандартные операции поиска по отсортированным спискам:8586```python87def index(a, x):88    'Locate the leftmost value exactly equal to x'89    i = bisect_left(a, x)90    if i != len(a) and a[i] == x:91        return i92    raise ValueError9394def find_lt(a, x):95    'Find rightmost value less than x'96    i = bisect_left(a, x)97    if i:98        return a[i-1]99    raise ValueError100101def find_le(a, x):102    'Find rightmost value less than or equal to x'103    i = bisect_right(a, x)104    if i:105        return a[i-1]106    raise ValueError107108def find_gt(a, x):109    'Find leftmost value greater than x'110    i = bisect_right(a, x)111    if i != len(a):112        return a[i]113    raise ValueError114115def find_ge(a, x):116    'Find leftmost item greater than or equal to x'117    i = bisect_left(a, x)118    if i != len(a):119        return a[i]120    raise ValueError121```122123## Примеры124125Функция [`bisect()`](https://python-all.ru/3.10/library/bisect.html#module-bisect) может быть полезна для поиска в числовых таблицах. В этом примере [`bisect()`](https://python-all.ru/3.10/library/bisect.html#module-bisect) используется для определения буквенной оценки за экзамен (скажем) на основе набора упорядоченных числовых порогов: 90 и выше – «A», 80–89 – «B» и так далее:126127```python128>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):129...     i = bisect(breakpoints, score)130...     return grades[i]131...132>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]133['F', 'A', 'C', 'C', 'B', 'A', 'A']134```135136Функции [`bisect()`](https://python-all.ru/3.10/library/bisect.html#module-bisect) и [`insort()`](https://python-all.ru/3.10/library/bisect.html#bisect.insort) также работают со списками кортежей. Аргумент *key* может использоваться для извлечения поля, по которому упорядочиваются записи в таблице:137138```python139>>> from collections import namedtuple140>>> from operator import attrgetter141>>> from bisect import bisect, insort142>>> from pprint import pprint143144>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))145146>>> movies = [147...     Movie('Jaws', 1975, 'Speilberg'),148...     Movie('Titanic', 1997, 'Cameron'),149...     Movie('The Birds', 1963, 'Hitchcock'),150...     Movie('Aliens', 1986, 'Scott')151... ]152153>>> # Найти первый фильм, выпущенный после 1960 года154>>> by_year = attrgetter('released')155>>> movies.sort(key=by_year)156>>> movies[bisect(movies, 1960, key=by_year)]157Movie(name='The Birds', released=1963, director='Hitchcock')158159>>> # Вставить фильм, сохраняя порядок сортировки160>>> romance = Movie('Love Story', 1970, 'Hiller')161>>> insort(movies, romance, key=by_year)162>>> pprint(movies)163[Movie(name='The Birds', released=1963, director='Hitchcock'),164 Movie(name='Love Story', released=1970, director='Hiller'),165 Movie(name='Jaws', released=1975, director='Speilberg'),166 Movie(name='Aliens', released=1986, director='Scott'),167 Movie(name='Titanic', released=1997, director='Cameron')]168```169170Если ключевая функция требует больших вычислительных затрат, можно избежать повторных вызовов функции, выполнив поиск по списку предварительно вычисленных ключей для нахождения индекса записи:171172```python173>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]174>>> data.sort(key=lambda r: r[1])       # Или используйте operator.itemgetter(1).175>>> keys = [r[1] for r in data]         # Предварительно вычислите список ключей.176>>> data[bisect_left(keys, 0)]177('black', 0)178>>> data[bisect_left(keys, 1)]179('blue', 1)180>>> data[bisect_left(keys, 5)]181('red', 5)182>>> data[bisect_left(keys, 8)]183('yellow', 8)184```185