Что такое бинарный поиск?

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

Пример на Python:

from typing import List, Optional

def binary_search(arr: List[int], target: int) -> Optional[int]:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return None

# Использование
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7))  # Выведет индекс 3

Важно, что бинарный поиск применим только к отсортированным данным.