Двоичный поиск

Коротко: Двоичный поиск находит элемент в отсортированном списке, многократно деля диапазон поиска пополам, — вместо того чтобы проверять все элементы по одному.

Подробнее: Он сравнивает искомое значение со средним элементом: если оно меньше, продолжает слева, если больше — справа. Поэтому для n элементов нужно лишь около log₂(n) шагов — для миллиона элементов самое большее 20 (время O(log n), см. О-нотация). Условие — отсортированный набор данных с доступом по индексу.

Подробности

def binary_search(items, target):

См. также: алгоритмы, сортировка, О-нотация, индекс массива