Урок 8: Бинарный поиск

Сыграем в угадайку: я загадал число от 1 до 100, и на каждую попытку я говорю «слишком много» или «слишком мало». Умный ход: каждый раз угадывать середину и отбрасывать половину вариантов. Это и есть «бинарный поиск» — алгоритм, который находит значение в отсортированном списке, вдвое сокращая число

Бинарный поиск похож на поиск слова в толстом словаре: вы не читаете страницу за страницей с начала. Вы открываете на середине, и если ваше слово идёт позже по алфавиту, вы разом отбрасываете всю первую половину. Каждый взгляд сокращает вдвое то, что осталось искать.

бинарный поиск: Алгоритм поиска на отсортированном массиве, который на каждом шаге проверяет середину и отбрасывает ту половину, которая не может содержать искомое значение — O(log n).
логарифмическое время: O(log n): число шагов растёт очень медленно — каждое удвоение n добавляет всего один шаг, потому что пространство поиска каждый раз делится пополам.
пространство поиска: Диапазон индексов [low, high], который ещё может содержать искомое значение; бинарный поиск сокращает его вдвое на каждой итерации.