все Python 3bisectфункция

bisect.bisect_left()

позиция

Возвращает индекс, куда вставить x в отсортированный список, чтобы порядок сохранился — ПЕРЕД уже равными элементами. Поиск за O(log n).

Синтаксис

bisect.bisect_left(a, x, lo=0, hi=len(a))

Список обязан быть отсортирован — проверки нет, на неотсортированных данных функция молча вернёт бессмысленный индекс. И O(log n) относится только к поиску: сама вставка через insort остаётся O(n), потому что список сдвигает хвост, так что bisect не превращает list в быструю сортированную структуру при массовых вставках.

Примеры

import bisect
a = [1, 3, 3, 5, 7]
bisect.bisect_left(a, 3) # → 1 (перед равными)
bisect.bisect_left(a, 4) # → 3
bisect.bisect_left(a, 8) # → 5

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности