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

Двоичный поиск имеет временную сложность O(log n). Это означает, что время выполнения алгоритма растёт логарифмически относительно размера входных данных.

Почему?
На каждом шаге алгоритм делит массив пополам, исключая половину элементов из рассмотрения. Для массива из n элементов максимальное количество шагов равно log₂(n).

Пример:

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

Примечание:

• Требуется отсортированный массив.
• Пространственная сложность — O(1) (итеративная реализация).