Бинарный поиск в Python: от новичка до мастера

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

Вы когда-нибудь ждали, пока линейный поиск переберёт миллион элементов? Бинарный поиск сокращает это время с O(n) до O(log n) — то есть вместо миллиона шагов нужно всего 20. Это не просто алгоритм, а суперсила для решения задач, где данные упорядочены. В этой статье вы не просто запомните шаги, а поймёте, как и почему это работает, и сможете применять бинарный поиск в реальных проектах и на собеседованиях.

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

Представьте, что вы ищете слово в словаре. Вы не листаете каждую страницу подряд, а открываете книгу примерно посередине. Если нужное слово находится слева, вы отбрасываете правую половину и повторяете процесс. Каждое сравнение уменьшает область поиска вдвое. Именно это и делает бинарный поиск.

Главное условие: данные должны быть отсортированы. Бинарный поиск использует порядок, чтобы гарантированно отбрасывать половину элементов на каждом шаге.

Инвариант: на каждом шаге искомый элемент (если он существует) находится в интервале [low, high]. Мы поддерживаем этот инвариант, сдвигая границы.

• Если значение в середине меньше искомого — сдвигаем low в mid + 1 (правая половина).
• Если больше — сдвигаем high в mid - 1 (левая половина).
• Когда low > high — интервал пуст, элемента нет.

Пример кода: классический бинарный поиск

def binary_search(arr, target):
    """
    Бинарный поиск в отсортированном массиве.
    Возвращает индекс target, если найден, иначе -1.
    """
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2  # безопасное вычисление середины
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # не найден

# Проверка
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7))  # 3
print(binary_search(arr, 2))  # -1

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

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

Задача из собеседований: поиск первой плохой версии

Представьте, что у вас есть n версий продукта, и после некоторой версии все последующие — плохие. Нужно найти первую плохую версию, вызывая API is_bad(version).

Линейный подход (O(n)):

def first_bad_version_linear(n, is_bad):
    for i in range(1, n + 1):
        if is_bad(i):
            return i
    return -1

Бинарный подход (O(log n)):

def first_bad_version(n, is_bad):
    low, high = 1, n
    while low <= high:
        mid = low + (high - low) // 2
        if is_bad(mid):
            high = mid - 1  # возможно, есть более ранняя плохая
        else:
            low = mid + 1
    # low указывает на первую плохую версию
    return low if low <= n and is_bad(low) else -1

Как это работает: инвариант — все версии до low хорошие, после high — плохие. В конце low — первый кандидат.

Другой пример: поиск места вставки

Задача: дан отсортированный массив и целевое число. Если число есть — вернуть его индекс; если нет — вернуть индекс, куда его можно вставить, сохранив порядок.

def search_insert(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return low  # позиция вставки

print(search_insert([1,3,5,6], 5))  # 2
print(search_insert([1,3,5,6], 2))  # 1

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

Бинарный поиск — это не просто алгоритм, а способ мышления. Любую задачу, где можно монотонно проверять условие на диапазоне, можно свести к бинарному поиску. Например: найти минимальную вместимость корабля для перевозки грузов за D дней, или наименьшее число, квадрат которого больше заданного. Освоив бинарный поиск, вы перестанете писать линейные переборы и начнёте видеть эффективные решения там, где другие видят только O(n).

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

Прямо сейчас возьмите любую задачу, которую вы недавно решили линейным поиском (например, поиск первого дубликата в отсортированном списке или проверку, является ли число полным квадратом). Перепишите её с использованием бинарного поиска. Попробуйте — и вы почувствуете разницу. Удачи!