Бинарный поиск

Зачем нужен бинарный поиск

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

Он полезен не только для вопроса «есть ли число в массиве». Та же схема помогает находить границы диапазонов, первую или последнюю подходящую позицию, работать со сдвинутыми отсортированными массивами и даже искать минимальное или максимальное значение, для которого выполняется некоторое условие.

Что входит в раздел

• Основы бинарного поиска. Разберём идею деления области поиска пополам и условия, без которых этот подход не работает.
• Поиск в отсортированном массиве. Соберём классический итеративный шаблон, который возвращает позицию найденного элемента.
• Lower Bound и Upper Bound. Научимся искать не конкретное значение, а первую позицию относительно заданной границы.
• Первая и последняя позиция. Используем поиск границ, когда одинаковое значение встречается несколько раз.
• Циклически сдвинутый отсортированный массив. Увидим, как сохранить идею бинарного поиска, даже если привычный глобальный порядок нарушен сдвигом.
• Бинарный поиск по ответу. Перенесём тот же принцип с индексов массива на пространство возможных ответов.

Главная мысль

int mid = left + (right - left) / 2;

if (values[mid] < target) {
    left = mid + 1;
} else {
    right = mid;
}

Ключ здесь не в формуле середины, а в том, что после проверки середины можно доказанно исключить одну часть диапазона. В следующих темах мы постепенно научимся формулировать это доказательство для разных задач.