bisect.md

1> **Источник:** https://python-all.ru/3.1/library/bisect.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# 8.5. `bisect` – Алгоритм бисекции массива89Этот модуль позволяет поддерживать список в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков элементов с дорогостоящими операциями сравнения такой подход может быть эффективнее более распространённых. Модуль называется `bisect`, потому что использует простой алгоритм бисекции. Исходный код может быть особенно полезен как рабочий пример этого алгоритма (граничные условия уже корректны!).1011Предоставляются следующие функции:1213#### `bisect.bisect_left(a, x, lo=0, hi=len(a))`1415Находит точку вставки для *x* в *a*, чтобы сохранить отсортированный порядок. Параметры *lo* и *hi* могут использоваться для указания подмножества списка, которое следует рассматривать; по умолчанию используется весь список. Если *x* уже присутствует в *a*, точка вставки будет находиться перед (левее) любых существующих элементов. Возвращаемое значение подходит для использования в качестве первого параметра `list.insert()`, при условии что *a* уже отсортирован.1617Возвращаемая точка вставки *i* делит массив *a* на две половины так, что `all(val < x for val in a[lo:i])` для левой стороны и `all(val >= x for val in a[i:hi])` для правой стороны.1819#### `bisect.bisect_right(a, x, lo=0, hi=len(a))`2021#### `bisect.bisect(a, x, lo=0, hi=len(a))`2223Аналогично [`bisect_left()`](https://python-all.ru/3.1/library/bisect.html#bisect.bisect_left), но возвращает точку вставки, которая находится после (правее) любых существующих вхождений *x* в *a*.2425Возвращаемая точка вставки *i* делит массив *a* на две половины так, что `all(val <= x for val in a[lo:i])` для левой стороны и `all(val > x for val in a[i:hi])` для правой стороны.2627#### `bisect.insort_left(a, x, lo=0, hi=len(a))`2829Вставляет3031*x*3233в3435*a*3637в отсортированном порядке. Это эквивалентно3839`a.insert(bisect.bisect_left(a, x, lo, hi), x)`4041при условии, что4243*a*4445уже отсортирован. Следует помнить, что поиск O(log n) перевешивается медленным шагом вставки O(n).4647#### `bisect.insort_right(a, x, lo=0, hi=len(a))`4849#### `bisect.insort(a, x, lo=0, hi=len(a))`5051Аналогично5253[`insort_left()`](https://python-all.ru/3.1/library/bisect.html#bisect.insort_left)5455, но вставляет5657*x*5859в6061*a*6263после любых существующих вхождений6465*x*6667.6869> **См. также**70>71> Рецепт [SortedCollection](https://python-all.ru/3.1/library/bisect.html), использующий bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой ключевой функции. Ключи предварительно вычисляются, чтобы избежать лишних вызовов ключевой функции во время поиска.7273## 8.5.1. Поиск в отсортированных списках7475Вышеупомянутые функции [`bisect()`](https://python-all.ru/3.1/library/bisect.html#bisect.bisect) полезны для поиска точек вставки, но могут быть сложными или неудобными для типичных задач поиска. Следующие пять функций показывают, как преобразовать их в стандартные операции поиска для отсортированных списков:7677```python78def index(a, x):79    'Locate the leftmost value exactly equal to x'80    i = bisect_left(a, x)81    if i != len(a) and a[i] == x:82        return i83    raise ValueError8485def find_lt(a, x):86    'Find rightmost value less than x'87    i = bisect_left(a, x)88    if i:89        return a[i-1]90    raise ValueError9192def find_le(a, x):93    'Find rightmost value less than or equal to x'94    i = bisect_right(a, x)95    if i:96        return a[i-1]97    raise ValueError9899def find_gt(a, x):100    'Find leftmost value greater than x'101    i = bisect_right(a, x)102    if i != len(a):103        return a[i]104    raise ValueError105106def find_ge(a, x):107    'Find leftmost item greater than or equal to x'108    i = bisect_left(a, x)109    if i != len(a):110        return a[i]111    raise ValueError112```113114## 8.5.2. Другие примеры115116Функция [`bisect()`](https://python-all.ru/3.1/library/bisect.html#bisect.bisect) может быть полезна для числовых табличных поисков. В этом примере [`bisect()`](https://python-all.ru/3.1/library/bisect.html#bisect.bisect) используется для поиска буквенной оценки за экзамен (скажем) на основе набора упорядоченных числовых границ: 90 и выше – «A», 80–89 – «B», и так далее:117118```python119>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):120...     i = bisect(breakpoints, score)121...     return grades[i]122...123>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]124['F', 'A', 'C', 'C', 'B', 'A', 'A']125```126127В отличие от функции [`sorted()`](https://python-all.ru/3.1/library/functions.html#sorted), не имеет смысла для функций [`bisect()`](https://python-all.ru/3.1/library/bisect.html#bisect.bisect) иметь аргументы *key* или *reversed*, потому что это привело бы к неэффективной реализации (последовательные вызовы функций bisect не «запоминали» бы все предыдущие поиски ключей).128129Вместо этого лучше выполнять поиск по списку предварительно вычисленных ключей, чтобы найти индекс нужной записи:130131```python132>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]133>>> data.sort(key=lambda r: r[1])134>>> keys = [r[1] for r in data]         # предварительно вычисленный список ключей135>>> data[bisect_left(keys, 0)]136('black', 0)137>>> data[bisect_left(keys, 1)]138('blue', 1)139>>> data[bisect_left(keys, 5)]140('red', 5)141>>> data[bisect_left(keys, 8)]142('yellow', 8)143```144