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

Честно признаться, раньше я боялся вопросов вроде «Дан отсортированный массив…». Моя первая попытка была неуклюжим линейным сканированием — как искать световой меч на свалке, перетряхивая каждую деталь. Я смотрел на часы, моя уверенность таяла, и я гадал, пройду ли когда-нибудь отбор. Однажды дождливым вторником, после очередного отклонённого решения, я сел с чашкой кофе и спросил себя: почему бинарный поиск кажется волшебством? Ответ был не в запоминании шаблона, а в понимании причины деления пополам. Как только я это осознал, алгоритм перестал быть заклинанием и стал надёжным инструментом, который я применяю везде, где данные отсортированы.

Суть бинарного поиска

Представьте отсортированный список как коридор с дверями от 1 до N, и приз (ваша цель) за одной из них. Поскольку двери упорядочены, если вы заглянете за дверь mid и увидите число меньше приза, вы можете уверенно захлопнуть все двери слева — ни одна из них не может содержать приз. Аналогично, если число больше, вы отбрасываете правую половину. Это ключевое понимание: каждое сравнение устраняет половину оставшегося пространства поиска. Мы не проверяем каждый элемент; мы используем гарантию упорядоченности, чтобы сократить размер задачи экспоненциально. После k шагов размер интервала равен N / 2ᵏ. Когда он становится единицей, мы нашли ответ — или убедились, что его нет. Вот почему время работы O(log N), а не O(N).

Красота в том, что эта логика работает для любого монотонного предиката, не только для простого равенства. Если вы можете ответить «Выполняется ли условие на индексе i?», и ответ переключается с false на true ровно один раз, бинарный поиск всё ещё применим. Именно поэтому он так часто встречается в задачах на собеседованиях.

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

Давайте сначала рассмотрим классическую реализацию, а затем разберём два реальных варианта для интервью. Я пишу на Python, потому что он чист, но та же логика переносится на любой язык.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2  # избегаем переполнения в других языках
        if arr[mid] == target:
            return mid  # нашли!
        elif arr[mid] < target:
            lo = mid + 1  # отбрасываем левую половину
        else:
            hi = mid - 1  # отбрасываем правую половину
    return -1  # не найдено

Частая ошибка #1 — off-by-one: если вы установите hi = mid вместо hi = mid - 1, когда arr[mid] > target, можно зациклиться, если цель отсутствует. Всегда сдвигайте границу за уже проверенный элемент.

Частая ошибка #2 — использование while lo < hi без пост-проверки: этот паттерн работает для поиска первого true, но при точном совпадении вы пропустите элемент, если не обработать последний индекс отдельно.

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

Вы продакт-менеджер, ведущий команду разработки нового продукта. К сожалению, последняя версия не прошла проверку качества. Поскольку каждая версия основана на предыдущей, все версии после плохой тоже плохи. Предположим, у вас есть n версий [1, 2, …, n], и вы хотите найти первую плохую. Вам дан API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для поиска первой плохой версии, минимизируя количество вызовов API.

Это идеальный случай для бинарного поиска по предикату isBadVersion(i). Предикат ложен для хороших версий и переключается на true на первой плохой, оставаясь true далее.

def first_bad_version(n):
    lo, hi = 1, n
    while lo < hi:
        mid = (lo + hi) // 2
        if isBadVersion(mid):
            hi = mid  # mid может быть первой плохой, сохраняем его
        else:
            lo = mid + 1  # mid хорошая, отбрасываем его и левую часть
    return lo  # lo == hi — это первая плохая

Обратите внимание: мы используем while lo < hi и возвращаем lo после выхода — дополнительная проверка не нужна, потому что мы ищем первое true.

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

Допустим, массив, отсортированный по возрастанию, повёрнут вокруг неизвестного вам пивота (например, [0,1,2,4,5,6,7] может стать [4,5,6,7,0,1,2]). Вам дано целевое значение. Если оно найдено, верните индекс, иначе -1. Время работы должно быть O(log n).

Массив не полностью отсортирован, но одна половина любого разбиения по mid всегда отсортирована. Мы можем решить, какую половину оставить, проверяя порядок.

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        # левая половина отсортирована?
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1  # цель в левой отсортированной части
            else:
                lo = mid + 1  # идём вправо
        else:
            # правая половина отсортирована
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1  # цель в правой отсортированной части
            else:
                hi = mid - 1  # идём влево
    return -1

Ключевое наблюдение — хотя бы одна сторона упорядочена — позволяет применить ту же логику отбрасывания половины, сохраняя O(log n).

Почему это важно

Освоение бинарного поиска — это не только прохождение собеседования; это формирование ментальной модели разделяй и властвуй. Всякий раз, когда вы встречаете монотонное свойство — будь то временные метки, баллы или скрытое условие вроде «приемлема ли задержка сети?» — вы можете сократить пространство поиска вдвое и решать задачи, которые иначе были бы линейными и медленными.

Представьте, что вы создаёте функцию поиска ближайшего свободного слота в календаре с тысячами записей. Линейный просмотр расстроит пользователей; бинарный поиск по отсортированным временам начала вернёт ответ за микросекунды. Или подумайте об отладке: вы можете бинарным поиском пройтись по истории коммитов git, чтобы найти точное изменение, вызвавшее баг (знаменитая команда git bisect делает именно это).

Как только вы усвоите принцип «отбрасывания половины», вы начнёте замечать возможности повсюду — больше никаких догадок, никакого перебора. Это похоже на то, как Нео уклоняется от пуль в «Матрице», когда алгоритм наконец наводится на цель: всё замедляется, и вы точно знаете, куда смотреть.

Практический вывод

Возьмите отсортированную коллекцию, с которой вы работаете — список ID пользователей, лог временных меток или таблицу лидеров. Напишите вспомогательную функцию бинарного поиска, которая находит первый элемент, удовлетворяющий вашему условию (например, первый балл ≥ 1000). Попробуйте, подкорректируйте границы и заметьте, как падает время выполнения.

Если чувствуете азарт, решите задачу «поиск в повёрнутом массиве» выше и добавьте дополнительный поворот: верните минимальный элемент в повороте (пивот).

Есть интересный кейс или вариация, с которой вы справились? Поделитесь в комментариях — я люблю узнавать, как разработчики превращают этот классический алгоритм в своё секретное оружие. Удачной охоты!