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

Зачем вам бинарный поиск?

Представьте: на собеседовании вам дают отсортированный массив из миллиона чисел и просят найти индекс цели. Ваш первый инстинкт — пройтись по всем элементам? Линейный поиск сделает до миллиона сравнений, а бинарный — всего около 20. Разница между «завалить собеседование» и «получить оффер». В этой статье вы не просто выучите алгоритм, а поймёте, как эксплуатировать порядок для сокращения пространства поиска вдвое на каждом шаге.

Как работает бинарный поиск: ключевая идея

Бинарный поиск — это алгоритм для поиска элемента в отсортированном массиве. Его сила в том, что каждое сравнение отбрасывает половину оставшихся элементов. Представьте игру: я загадал число от 1 до 100, а вы угадываете. Вы не будете перебирать по порядку — вы назовёте 50, я скажу «больше» или «меньше», и вы отбросите половину чисел. Так и здесь: после k шагов остаётся N / 2^k кандидатов. Чтобы диапазон сузился до одного элемента, нужно k = log₂ N шагов. Отсюда сложность O(log n).

Магия не в арифметике, а в инварианте: если цель существует, она всегда находится внутри текущего окна [low, high]. Мы никогда не выбрасываем сегмент, который может содержать ответ, потому что сравнение (mid < target или mid > target) точно указывает, какая половина неактуальна.

Реализация на Python

Вот классическая реализация бинарного поиска:

def binary_search(arr, target):
    """Бинарный поиск в отсортированном массиве.
    Возвращает индекс target или -1, если элемент не найден."""
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  # целочисленное деление
        guess = arr[mid]

        if guess == target:
            return mid           # нашли!
        elif guess < target:
            low = mid + 1        # цель справа
        else:
            high = mid - 1       # цель слева

    return -1                    # цели нет

Пояснение:
- Условие low <= high гарантирует, что мы не вышли за границы окна.
- mid делит окно пополам; сравнение говорит, какую половину отбросить.
- Обновляя low или high, мы сохраняем инвариант.

Пример использования:

nums = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(nums, 7))   # 3
print(binary_search(nums, 2))   # -1

Типичные ошибки (и как их избежать)

• Ошибка на единицу: забыть +1 или -1 при сдвиге границ — ведёт к бесконечному циклу или пропуску цели. Всегда обновляйте low = mid + 1 и high = mid - 1.
• Переполнение mid: в языках с фиксированными целыми (Java, C++) сумма low + high может переполниться. Безопасная формула: mid = low + (high - low) // 2. В Python проблем нет, но привычка полезная.
• Неверное условие цикла: low < high вместо low <= high — может пропустить элемент, когда low == high.

Бинарный поиск в реальных задачах с собеседований

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

Дан массив, который был отсортирован, а затем повёрнут в неизвестной точке. Найдите цель за O(log n).

Идея: Даже если массив не глобален, одна половина относительно середины всегда отсортирована. Определите, какая половина отсортирована, и решите, где искать.

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

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

Дан API isBadVersion(version), который возвращает True для плохих версий (все версии после первой плохой — тоже плохие). Найдите первую плохую версию.

Идея: Предикат монотонный (False...False, True...True). Бинарный поиск по предикату найдёт точку перехода.

def first_bad_version(n):
    low, high = 1, n
    while low < high:
        mid = (low + high) // 2
        if isBadVersion(mid):
            high = mid          # первая плохая версия <= mid
        else:
            low = mid + 1       # первая плохая версия > mid
    return low

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

Освоив бинарный поиск, вы перестанете автоматически использовать линейный перебор. Вместо этого вы начнёте задавать вопросы:

• Данные упорядочены? Можно ли навязать порядок?
• Даёт ли проверка чёткое направление (больше/меньше, True/False)?
• Можно ли поддерживать инвариант, сокращающий пространство поиска вдвое?

Если ответ «да», вы превращаете линейный перебор в логарифмический спринт. На практике это означает обработку миллионов записей за миллисекунды, быстрые API-поиски и восхищение интервьюеров.

Это также открывает путь к продвинутым техникам: экспоненциальный поиск, параллельный бинарный поиск и даже бинарный поиск по ответу (шаблон «поиск в пространстве решений» для задач вроде «минимальная скорость поедания бананов» или «грузоподъёмность для доставки»).

Ваше следующее задание

Закрепите навык: дана отсортированная двумерная матрица, где каждая строка и каждый столбец отсортированы по возрастанию. Напишите алгоритм поиска цели за O(m + n). Затем улучшите до O(log(m·n)), представив матрицу как плоский отсортированный массив и применив бинарный поиск.

Попробуйте, напишите код и поделитесь решением в комментариях. Увидим, как вы используете «кольцо всевластия» бинарного поиска в своих приключениях.

Держите массивы отсортированными, а мысли — ясными. И помните: иногда самые большие победы приходят от деления проблемы пополам, а не от пробивания её насквозь. Счастливого кода! 🚀