bisect.md

1> **Источник:** https://python-all.ru/2.7/library/bisect.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# 8.5. [`bisect`](https://python-all.ru/2.7/library/bisect.html#module-bisect) – алгоритм поиска вставки в массиве89Новое в версии 2.1.1011**Исходный код:** [Lib/bisect.py](https://python-all.ru/src/2.7/Lib/bisect.py)1213---1415Этот модуль поддерживает хранение списка в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков, где операции сравнения дороги, это может быть эффективнее более распространенного подхода. Модуль называется [`bisect`](https://python-all.ru/2.7/library/bisect.html#module-bisect), потому что использует базовый алгоритм деления пополам. Исходный код может быть полезным как рабочий пример этого алгоритма (граничные условия уже правильные!).1617Предоставляются следующие функции:1819#### `bisect.bisect_left(a, x, lo=0, hi=len(a))`2021Находит точку вставки для *x* в *a*, чтобы сохранить сортировку. Параметры *lo* и *hi* можно использовать для указания подмножества списка; по умолчанию используется весь список. Если *x* уже присутствует в *a*, точка вставки будет перед (левее) всех существующих вхождений. Возвращаемое значение можно использовать в качестве первого аргумента для `list.insert()`, если *a* уже отсортирован.2223Возвращаемая точка вставки *i* делит массив *a* на две половины так, что для левой части выполняется `all(val < x for val in a[lo:i])`, а для правой – `all(val >= x for val in a[i:hi])`.2425#### `bisect.bisect_right(a, x, lo=0, hi=len(a))`2627#### `bisect.bisect(a, x, lo=0, hi=len(a))`2829Аналогично [`bisect_left()`](https://python-all.ru/2.7/library/bisect.html#bisect.bisect_left), но возвращает точку вставки, которая находится после (правее) всех существующих вхождений *x* в *a*.3031Возвращаемая точка вставки *i* делит массив *a* на две половины так, что для левой части выполняется `all(val <= x for val in a[lo:i])`, а для правой – `all(val > x for val in a[i:hi])`.3233#### `bisect.insort_left(a, x, lo=0, hi=len(a))`3435Вставляет *x* в *a* в отсортированном порядке. Это эквивалентно `a.insert(bisect.bisect_left(a, x, lo, hi), x)` при условии, что *a* уже отсортирован. Следует помнить, что поиск за O(log n) незначителен по сравнению с медленной вставкой за O(n).3637#### `bisect.insort_right(a, x, lo=0, hi=len(a))`3839#### `bisect.insort(a, x, lo=0, hi=len(a))`4041Аналогично [`insort_left()`](https://python-all.ru/2.7/library/bisect.html#bisect.insort_left), но вставляет *x* в *a* после всех существующих вхождений *x*.4243> **См. также**44>45> Рецепт [SortedCollection](https://python-all.ru/2.7/library/bisect.html), использующий bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой ключевой функции. Ключи предварительно вычисляются, чтобы избежать лишних вызовов ключевой функции во время поиска.4647## 8.5.1. Поиск в отсортированных списках4849Вышеупомянутые функции [`bisect()`](https://python-all.ru/2.7/library/bisect.html#module-bisect) полезны для поиска точек вставки, но могут быть неудобны или сложны для обычных задач поиска. Следующие пять функций показывают, как преобразовать их в стандартные операции поиска по отсортированным спискам:5051```python52def index(a, x):53    'Locate the leftmost value exactly equal to x'54    i = bisect_left(a, x)55    if i != len(a) and a[i] == x:56        return i57    raise ValueError5859def find_lt(a, x):60    'Find rightmost value less than x'61    i = bisect_left(a, x)62    if i:63        return a[i-1]64    raise ValueError6566def find_le(a, x):67    'Find rightmost value less than or equal to x'68    i = bisect_right(a, x)69    if i:70        return a[i-1]71    raise ValueError7273def find_gt(a, x):74    'Find leftmost value greater than x'75    i = bisect_right(a, x)76    if i != len(a):77        return a[i]78    raise ValueError7980def find_ge(a, x):81    'Find leftmost item greater than or equal to x'82    i = bisect_left(a, x)83    if i != len(a):84        return a[i]85    raise ValueError86```8788## 8.5.2. Другие примеры8990Функция [`bisect()`](https://python-all.ru/2.7/library/bisect.html#module-bisect) может быть полезна для поиска в числовых таблицах. В этом примере [`bisect()`](https://python-all.ru/2.7/library/bisect.html#module-bisect) используется для определения буквенной оценки за экзамен (скажем) на основе набора упорядоченных числовых порогов: 90 и выше – «A», 80–89 – «B» и так далее:9192```python93>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):94        i = bisect(breakpoints, score)95        return grades[i]9697>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]98['F', 'A', 'C', 'C', 'B', 'A', 'A']99```100101В отличие от функции [`sorted()`](https://python-all.ru/2.7/library/functions.html#sorted), для функций [`bisect()`](https://python-all.ru/2.7/library/bisect.html#module-bisect) не имеет смысла иметь аргументы *key* или *reversed*, поскольку это привело бы к неэффективной реализации (последовательные вызовы функций bisect не «запоминали» бы все предыдущие поиски по ключу).102103Вместо этого лучше выполнять поиск по списку предварительно вычисленных ключей, чтобы найти индекс нужной записи:104105```python106>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]107>>> data.sort(key=lambda r: r[1])108>>> keys = [r[1] for r in data]         # предварительно вычисленный список ключей109>>> data[bisect_left(keys, 0)]110('black', 0)111>>> data[bisect_left(keys, 1)]112('blue', 1)113>>> data[bisect_left(keys, 5)]114('red', 5)115>>> data[bisect_left(keys, 8)]116('yellow', 8)117```118