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

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

Причины такой эффективности:

1. На каждом шаге алгоритм делит отсортированный массив (или его текущую часть) пополам, отбрасывая половину элементов, в которой искомого элемента точно нет.
2. Количество шагов, необходимых для нахождения элемента в массиве размера n, равно log₂n. Например, для 1024 элементов потребуется максимум 10 шагов (log₂1024 = 10).

Пример реализации на 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

# Пример использования:
sorted_list = [1, 5, 7, 10, 12, 15, 20, 22]
print(f"Индекс 10: {binary_search(sorted_list, 10)}") # Выведет 3
print(f"Индекс 6: {binary_search(sorted_list, 6)}")   # Выведет -1

Важное примечание: Сложность O(log n) справедлива только для отсортированных массивов. Если массив не отсортирован, его предварительная сортировка (например, с помощью Merge Sort или Quick Sort) будет иметь сложность O(n log n), которая будет доминировать над сложностью самого бинарного поиска. Таким образом, бинарный поиск наиболее эффективен, когда данные уже отсортированы или сортируются один раз для множества последующих поисков.