Бинарный поиск

Бинарный поиск (Binary Search): итеративная и рекурсивная реализации, пошаговый разбор, код на Python, сложность O(log n) и требования к данным.

Бинарный поиск работает только на отсортированном массиве. На каждом шаге он сравнивает цель со средним элементом и отбрасывает половину оставшегося диапазона. Это позволяет находить элемент за O(log n) шагов.

Сложность: O(log n); O(1) памяти для итеративного варианта, O(log n) для рекурсивного.

Идея алгоритма

Вспомни игру «угадай число от 1 до 100». Умный игрок называет 50. Если загадано 72 — он называет 75, затем 62, 68, 71, 72. За 7 вопросов — любое число от 1 до 100. Это и есть бинарный поиск: каждый вопрос вдвое сужает диапазон.

Пошаговый разбор

Отсортированный массив [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], ищем 23:

За 3 шага вместо 6 при линейном поиске. При 10 000 элементов бинарный поиск возьмёт не более 14 шагов.

Итеративная реализация

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1       # цель правее
        else:
            high = mid - 1      # цель левее
    return -1                   # не найден

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23))   # 5
print(binary_search(arr, 10))   # -1

Вывод:

5
-1

Рекурсивная реализация

def binary_search_rec(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, high)
    else:
        return binary_search_rec(arr, target, low, mid - 1)

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search_rec(arr, 56))   # 7
print(binary_search_rec(arr, 1))    # -1

Вывод:

7
-1

Сложность и свойства

Обязательное условие: массив должен быть отсортирован. Если данные поступают динамически — поддерживать их в упорядоченном виде помогают сбалансированные деревья (BST, AVL) или структура bisect в Python.

Когда применять

• Данные отсортированы и поиск выполняется многократно.
• Нужен быстрый ответ «есть ли элемент» в большом наборе данных.
• Поиск границы вставки (lower_bound / upper_bound) — стандартная задача в конкурентном программировании.

В Python стандартная библиотека предоставляет готовый бинарный поиск: import bisect; bisect.bisect_left(arr, target).

Коротко

• Бинарный поиск делит диапазон пополам на каждом шаге — только на отсортированных данных.
• O(log n) шагов: при n=1 000 000 хватит 20 сравнений.
• Итеративный вариант: O(1) памяти; рекурсивный: O(log n) стек.
• В Python — bisect, в Java — Arrays.binarySearch.