Что хотят услышать интервьюеры:

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

Определение:

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

Пример использования:

Найти число 23 в отсортированном списке.

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

nums = [3, 7, 11, 15, 23, 42, 56]
print(binary_search(nums, 23))  # 4

Пояснение кода:

left и right задают границы текущего диапазона поиска.
mid — середина диапазона.
Если элемент в mid равен target, поиск завершён.
Если arr[mid] < target, ищем только справа.
Если arr[mid] > target, ищем только слева.
Каждый шаг сокращает количество рассматриваемых элементов примерно в 2 раза, поэтому число итераций зависит от log2(n).

Ключевые моменты:

Бинарный поиск применим только к отсортированным данным.
Временная сложность: O(log n).
Памятная сложность у итеративной версии: O(1).
В худшем случае число сравнений примерно равно log2(n).
Если данные не отсортированы, бинарный поиск использовать нельзя без предварительной сортировки.

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