bisect.md

1> **Источник:** https://python-all.ru/3.4/library/bisect.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# 8.6. [`bisect`](https://python-all.ru/3.4/library/bisect.html#module-bisect) – алгоритм бинарного поиска в массиве89**Исходный код:** [Lib/bisect.py](https://python-all.ru/src/3.4/Lib/bisect.py)1011---1213Этот модуль позволяет поддерживать список в отсортированном состоянии без необходимости сортировать его после каждой вставки. Для длинных списков с дорогими операциями сравнения это может быть улучшением по сравнению с более распространённым подходом. Модуль называется [`bisect`](https://python-all.ru/3.4/library/bisect.html#module-bisect), потому что он использует базовый алгоритм бинарного поиска. Исходный код может быть полезен как рабочий пример алгоритма (граничные условия уже верны!).1415Предоставляются следующие функции:1617#### `bisect.bisect_left(a, x, lo=0, hi=len(a))`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#### `bisect.bisect_right(a, x, lo=0, hi=len(a))`2425#### `bisect.bisect(a, x, lo=0, hi=len(a))`2627Аналогично [`bisect_left()`](https://python-all.ru/3.4/library/bisect.html#bisect.bisect_left), но возвращает точку вставки, которая находится после (правее) любых существующих вхождений *x* в *a*.2829Возвращаемая точка вставки *i* делит массив *a* на две половины так, что `all(val <= x for val in a[lo:i])` для левой стороны и `all(val > x for val in a[i:hi])` для правой стороны.3031#### `bisect.insort_left(a, x, lo=0, hi=len(a))`3233Вставляет *x* в *a* в отсортированном порядке. Это эквивалентно `a.insert(bisect.bisect_left(a, x, lo, hi), x)` при условии, что *a* уже отсортирован. Следует помнить, что поиск O(log n) перевешивается медленным шагом вставки O(n).3435#### `bisect.insort_right(a, x, lo=0, hi=len(a))`3637#### `bisect.insort(a, x, lo=0, hi=len(a))`3839Аналогично [`insort_left()`](https://python-all.ru/3.4/library/bisect.html#bisect.insort_left), но вставляет *x* в *a* после любых существующих вхождений *x*.4041> **См. также**42>43> Рецепт [SortedCollection](https://python-all.ru/3.4/library/bisect.html), использующий bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой ключевой функции. Ключи предварительно вычисляются, чтобы избежать лишних вызовов ключевой функции во время поиска.4445## 8.6.1. Поиск в отсортированных списках4647Вышеупомянутые функции [`bisect()`](https://python-all.ru/3.4/library/bisect.html#module-bisect) полезны для поиска точек вставки, но могут быть сложными или неудобными для типичных задач поиска. Следующие пять функций показывают, как преобразовать их в стандартные операции поиска для отсортированных списков:4849```python50def index(a, x):51    'Locate the leftmost value exactly equal to x'52    i = bisect_left(a, x)53    if i != len(a) and a[i] == x:54        return i55    raise ValueError5657def find_lt(a, x):58    'Find rightmost value less than x'59    i = bisect_left(a, x)60    if i:61        return a[i-1]62    raise ValueError6364def find_le(a, x):65    'Find rightmost value less than or equal to x'66    i = bisect_right(a, x)67    if i:68        return a[i-1]69    raise ValueError7071def find_gt(a, x):72    'Find leftmost value greater than x'73    i = bisect_right(a, x)74    if i != len(a):75        return a[i]76    raise ValueError7778def find_ge(a, x):79    'Find leftmost item greater than or equal to x'80    i = bisect_left(a, x)81    if i != len(a):82        return a[i]83    raise ValueError84```8586## 8.6.2. Другие примеры8788Функция [`bisect()`](https://python-all.ru/3.4/library/bisect.html#module-bisect) может быть полезна для числовых табличных поисков. В этом примере [`bisect()`](https://python-all.ru/3.4/library/bisect.html#module-bisect) используется для поиска буквенной оценки за экзамен (скажем) на основе набора упорядоченных числовых границ: 90 и выше – «A», 80–89 – «B», и так далее:8990```python91>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):92...     i = bisect(breakpoints, score)93...     return grades[i]94...95>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]96['F', 'A', 'C', 'C', 'B', 'A', 'A']97```9899В отличие от функции [`sorted()`](https://python-all.ru/3.4/library/functions.html#sorted), не имеет смысла для функций [`bisect()`](https://python-all.ru/3.4/library/bisect.html#module-bisect) иметь аргументы *key* или *reversed*, потому что это привело бы к неэффективной реализации (последовательные вызовы функций bisect не «запоминали» бы все предыдущие поиски ключей).100101Вместо этого лучше выполнять поиск по списку предварительно вычисленных ключей, чтобы найти индекс нужной записи:102103```python104>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]105>>> data.sort(key=lambda r: r[1])106>>> keys = [r[1] for r in data]         # предварительно вычисленный список ключей107>>> data[bisect_left(keys, 0)]108('black', 0)109>>> data[bisect_left(keys, 1)]110('blue', 1)111>>> data[bisect_left(keys, 5)]112('red', 5)113>>> data[bisect_left(keys, 8)]114('yellow', 8)115```116