все Python 3bisectпонятие

Бинарный поиск через bisect

применение

bisect не проверяет наличие элемента, но можно реализовать бинарный поиск, проверив найденную позицию.

Синтаксис

i = bisect_left(a, x)
if i < len(a) and a[i] == x: found

Порядок условий важен: i < len(a) должно стоять первым, иначе для x больше всех элементов a[i] выбросит IndexError. Брать нужно именно bisect_left — bisect_right вернул бы позицию за найденным элементом, и сравнивать пришлось бы с a[i-1]. Смысл затеи — заменить O(n)-проверку x in a на O(log n), но это работает только на заранее отсортированном списке.

Примеры

import bisect
def search(a, x):
    i = bisect.bisect_left(a, x)
    return i if i < len(a) and a[i] == x else -1
a = [1, 3, 5, 7, 9]
print(search(a, 5))  # → 2
print(search(a, 4))  # → -1
print(search(a, 9))  # → 4

См. также

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