Для закрепления рассмотрим несколько примеров. В первом случае элемент отсутствует в массиве:

sorted_data = [11, 12, 22, 25, 34, 64, 90]
target = 50
print(binary_search(sorted_data, target))  # Вывод: -1

Алгоритм выполнит следующие шаги: сначала проверит середину (25), затем, так как 25 меньше 50, перейдет к правой половине [34, 64, 90]. Проверив элемент 64, который больше 50, он перейдет к левой части этого подмассива, [34]. После сравнения 34 с 50 границы low и high пересекутся, и будет возвращено значение -1.

Поиск первого и последнего элементов также работает корректно:

sorted_data = [11, 12, 22, 25, 34, 64, 90]
target = 11
print(binary_search(sorted_data, target))  # Вывод: 0

target = 90
print(binary_search(sorted_data, target))  # Вывод: 6

Главное преимущество бинарного поиска — его исключительная эффективность. Сложность алгоритма оценивается как O(log n), что означает логарифмическую зависимость количества операций от размера данных. Это становится возможным благодаря тому, что на каждом шаге область поиска сокращается вдвое. Например, для массива из 100 элементов в худшем случае потребуется не более 7 проверок, для миллиона элементов — около 20. В сравнении с линейным поиском, который в худшем случае проверяет все элементы, выигрыш становится колоссальным, особенно на больших объемах данных.

Теперь обратимся к ключевому вопросу: почему бинарный поиск неприменим к неотсортированным данным? Вся логика алгоритма строится на предположении, что если элемент в середине меньше искомого, то все элементы слева от него тоже заведомо меньше. Это свойство гарантировано только в отсортированном массиве. В противном случае, отбросив какую-либо половину, мы можем случайно потерять искомый элемент. Проиллюстрируем это на примере массива [64, 11, 90, 22, 25, 12, 34]. При поиске числа 90 алгоритм, проверив середину (22), решит, что нужно искать справа, так как 22 меньше 90. Однако правая часть [25, 12, 34] не содержит 90, хотя само число 90 присутствует в исходном массиве слева от проверяемой середины. Таким образом, на несортированных данных бинарный поиск дает ненадежный результат.

Алгоритм можно реализовать не только итеративно, но и с помощью рекурсии, когда функция вызывает саму себя для суженной области поиска.

def binary_search_recursive(arr, target, low, high):
    """Рекурсивная версия бинарного поиска."""
    
    # Базовый случай: область поиска пуста
    if low > high:
        return -1
    
    # Находим середину
    mid = (low + high) // 2
    
    # Проверяем средний элемент
    if arr[mid] == target:
        return mid  # Нашли!
    elif arr[mid] < target:
        # Рекурсивно ищем в правой половине
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        # Рекурсивно ищем в левой половине
        return binary_search_recursive(arr, target, low, mid - 1)


# Использование:
sorted_data = [11, 12, 22, 25, 34, 64, 90]
target = 22
result = binary_search_recursive(sorted_data, target, 0, len(sorted_data) - 1)
print(result)  # Вывод: 2

Рекурсивная версия часто выглядит более лаконичной, но она использует память для стека вызовов, что может стать ограничением для очень больших массивов. Итеративный подход с циклом обычно более эффективен с точки зрения потребления памяти.

Интересно, что принцип бинарного поиска интуитивно используется людьми в повседневных задачах. Самый яркий пример — поиск слова в бумажном словаре. Мы открываем книгу примерно посередине, смотрим на букву, определяем, нужная ли она нам, и отбрасываем одну из половин. Этот процесс повторяется до нахождения нужной страницы. Точно так же мы действуем, ища дату в календаре или настраивая громкость. Все эти ситуации объединяет наличие упорядоченных данных и стратегия последовательного деления области поиска.