bisect – алгоритм бисекции массива¶bisect – Array bisection algorithm

Этот модуль позволяет поддерживать список в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков элементов с дорогостоящими операциями сравнения такой подход может быть эффективнее более распространённых. Модуль называется bisect, потому что использует простой алгоритм бисекции. Исходный код может быть особенно полезен как рабочий пример этого алгоритма (граничные условия уже корректны!).

Предоставляются следующие функции:

bisect.bisect_left(list, item[, lo[, hi]])¶

Находит подходящую точку вставки для item в list, чтобы сохранить упорядоченность. Параметры lo и hi можно использовать для указания подмножества списка, которое следует рассматривать; по умолчанию используется весь список. Если item уже присутствует в list, точка вставки будет перед (левее) любых существующих записей. Возвращаемое значение подходит для использования в качестве первого параметра list.insert(). Предполагается, что list уже отсортирован.

bisect.bisect_right(list, item[, lo[, hi]])¶

Похожа на bisect_left(), но возвращает точку вставки, которая находится после (правее) любых существующих записей item в list.

bisect.bisect(...)¶

Псевдоним bisect_right().

bisect.insort_left(list, item[, lo[, hi]])¶

Вставляет item в list в отсортированном порядке. Это эквивалентно list.insert(bisect.bisect_left(list, item, lo, hi), item). Предполагается, что list уже отсортирован.

bisect.insort_right(list, item[, lo[, hi]])¶

Похожа на insort_left(), но вставляет item в list после любых существующих записей item.

bisect.insort(...)¶

Псевдоним insort_right().

>>> grades = "FEDCBA"
>>> breakpoints = [30, 44, 66, 75, 85]
>>> from bisect import bisect
>>> def grade(total):
...           return grades[bisect(breakpoints, total)]
...
>>> grade(66)
'C'
>>> map(grade, [33, 99, 77, 44, 12, 88])
['E', 'A', 'B', 'D', 'F', 'A']