Бинарный поиск: как отсекать половину массива за O(log n)

Почему бинарный поиск — ваш главный инструмент

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

Как работает бинарный поиск: интуиция и математика

Бинарный поиск — это стратегия «разделяй и властвуй». Мы смотрим на средний элемент отсортированного массива и сравниваем его с искомым числом. Если средний элемент равен цели — ура, нашли. Если цель меньше — значит, она может быть только в левой половине (все элементы справа больше). Если больше — ищем справа. Каждое сравнение сокращает область поиска вдвое.

Почему это так эффективно? После k шагов мы просматриваем не более n / 2^k элементов. Как только это число становится меньше 1, поиск завершён. Значит, k = ⌈log₂ n⌉. Для массива из 1 000 000 элементов это всего 20 шагов. Время работы — O(log n), дополнительная память — O(1) (только несколько переменных).

Пишем бинарный поиск на Python: от простого к сложному

Наивный подход (линейный поиск)

def linear_search(arr, target):
    """Проходит по всему массиву — медленно на больших данных."""
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Код простой, но на собеседовании такой ответ обычно встречают вопросом: «А можно быстрее?»

Правильная реализация бинарного поиска

def binary_search(arr, target):
    """
    Возвращает индекс target в отсортированном списке arr,
    или -1, если элемент не найден.
    """
    left, right = 0, len(arr) - 1  # границы включительно

    while left <= right:           # пока есть пространство поиска
        mid = (left + right) // 2  # индекс середины
        mid_val = arr[mid]

        if mid_val == target:
            return mid             # нашли!
        elif mid_val < target:
            left = mid + 1         # цель в правой половине
        else:
            right = mid - 1        # цель в левой половине

    return -1                      # не найдено

Типичные ошибки новичков

• Ошибка на единицу: использование left < right вместо left <= right может привести к пропуску элемента.
• Переполнение: в языках с фиксированной разрядностью (left + right) // 2 может вызвать переполнение. В Python это не проблема, но в Java/C++ пишут mid = left + (right - left) // 2.
• Неотсортированный массив: бинарный поиск работает только на отсортированных данных. Если массив не отсортирован, результат будет бессмысленным.

Разбор задач с собеседований

Задача 1: Поиск в повёрнутом отсортированном массиве

«Дан отсортированный массив, который был циклически сдвинут в неизвестной точке. Найдите индекс целевого элемента.»

Решение: определите, какая половина осталась нормально отсортированной, и примените к ней стандартный бинарный поиск.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        # Левая половина отсортирована?
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Правая половина отсортирована
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Задача 2: Первая плохая версия

«У вас есть n версий продукта. Функция is_bad_version(k) возвращает True, если версия k бракованная. Найдите первую бракованную версию.»

Это классический поиск границы. Бинарный поиск идеально подходит.

def first_bad_version(n):
    left, right = 1, n
    while left < right:
        mid = left + (right - left) // 2
        if is_bad_version(mid):
            right = mid  # брак начиная с mid или раньше
        else:
            left = mid + 1  # версия хорошая, ищем после mid
    return left  # left == right — первая плохая версия

Обратите внимание: условие left < right и сужение правой границы до mid (а не mid - 1) позволяют найти первый элемент, удовлетворяющий предикату.

Где ещё применяется бинарный поиск

Бинарный поиск — это не только про массивы. Он лежит в основе:

• Баз данных: B-деревья используют бинарный поиск для логарифмического доступа к записям.
• Компьютерной графики: структуры ускорения трассировки лучей (BVH) делят пространство пополам.
• Повседневных задач: поиск порога, минимального значения, удовлетворяющего условию, или первого сбоя в CI-пайплайне.

Как только вы проникнетесь идеей «отсекай половину», вы начнёте замечать возможности заменить O(n) на O(log n) повсюду: от балансировки таблицы лидеров до автодополнения текста.

Ваше задание

Закрепите навык: дан отсортированный массив целых чисел, который может содержать дубликаты. Найдите индекс первого вхождения целевого значения. Реализуйте бинарный поиск — подумайте, что делать, когда нашли совпадение. Попробуйте написать код прямо сейчас.

Бинарный поиск — это джедайский приём, который превращает вас из новичка с тупым мечом в мастера, отражающего бластерные выстрелы одним движением. И всё это — всего несколько строк кода. Да пребудет с вами сила (и логарифм)!