Какова временная и пространственная сложность данного алгоритма?

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

Ниже пример реализации на Python:

def binary_search(arr, target):
    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 -1

Разбираю по шагам:

• Каждую итерацию цикла размер рабочей области уменьшается вдвое. Начальный размер — n, после i итераций — n / 2^i.
• Цикл выполняется, пока n / 2^i ≥ 1 → i ≤ log₂(n). Значит, максимум log₂(n) + 1 итераций.
• Каждая итерация содержит константное число операций (вычисление mid, одно сравнение, присваивание).
• Итоговая временная сложность: O(log n) (логарифмическая).
• Память: мы используем только три переменные (left, right, mid), их размер не зависит от n → O(1) (константная).

Важно уточнить: логарифм здесь по основанию 2, но в Big O основание не указывают — O(log n) подразумевает логарифмический рост. Для несортированного массива бинарный поиск не применим; если бы массив был не отсортирован, пришлось бы сначала его отсортировать (O(n log n)), что меняло бы общую сложность. Пространственная сложность O(1) верна только для итеративной версии; рекурсивная версия потребовала бы O(log n) памяти для стека вызовов.