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

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

Двоичный поиск — один из наиболее эффективных алгоритмов поиска. Давайте разберемся с его сложностью.

Основной результат

Временная сложность: O(log n)

• n — количество элементов в отсортированном массиве
• log n — логарифм по основанию 2

Почему именно O(log n)?

Двоичный поиск работает путём деления массива пополам на каждом шаге:

# Начальный массив
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]  # 10 элементов

# Итерация 1: проверяем середину
# mid = 9, нам нужно 7 -> левая половина
# Осталось 5 элементов [1, 3, 5, 7, 9]

# Итерация 2: проверяем середину
# mid = 5, нам нужно 7 -> правая половина  
# Осталось 3 элемента [7, 9]

# Итерация 3: проверяем середину
# mid = 7, нашли!
# Осталось 1 элемент

После каждой итерации пространство поиска уменьшается в 2 раза:

• n элементов → n/2 → n/4 → n/8 → ... → 1

Количество таких делений = log₂(n)

# Примеры:
# n = 1,000     → log₂(1000) ≈ 10 итераций
# n = 1,000,000 → log₂(1000000) ≈ 20 итераций
# n = 1 млрд   → log₂(1000000000) ≈ 30 итераций

Реализация двоичного поиска

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # Нашли за O(log n) операций
        elif arr[mid] < target:
            left = mid + 1  # Ищем в правой половине
        else:
            right = mid - 1  # Ищем в левой половине
    
    return -1  # Не найдено

# Использование
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
result = binary_search(arr, 12)
print(result)  # 5 (индекс элемента)

Сравнение с линейным поиском

# Линейный поиск: O(n)
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Двоичный поиск: O(log n)
# Очень большая разница!

Сравнение производительности:

Размер массива  | Линейный поиск | Двоичный поиск | Разница
100             | 100 операций   | 7 операций     | 14x быстрее
10,000          | 10,000         | 14             | 714x
1,000,000       | 1,000,000      | 20             | 50,000x
1 миллиард      | 1,000,000,000  | 30             | 33 млн x

Полная анализ сложности

Лучший случай: O(1)

# Элемент находится в центре массива на первой же итерации
arr = [1, 5, 9]  # target = 5
# Одна итерация: найдено!

Средний случай: O(log n)

# Элемент в произвольном месте
# В среднем нужно log₂(n) проверок

Худший случай: O(log n)

# Элемента нет в массиве или он в самом конце
# Всё равно нужно log₂(n) проверок до конца

Пространственная сложность

Итеративная реализация: O(1)

# Используем только несколько переменных: left, right, mid
def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    # O(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(log n)

# Каждый рекурсивный вызов добавляет кадр в стек вызовов
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
    # O(log n) в стеке вызовов

Важное условие

Двоичный поиск работает ТОЛЬКО на отсортированном массиве!

# ✅ Работает
arr = [1, 3, 5, 7, 9, 11]  # Отсортирован
binary_search(arr, 7)  # Работает корректно

# ❌ Не работает
arr = [3, 1, 9, 5, 11, 7]  # Не отсортирован
binary_search(arr, 7)  # Неопределённый результат

Практические применения

# 1. Встроенный bisect модуль
import bisect

arr = [1, 3, 5, 7, 9, 11]
index = bisect.bisect_left(arr, 7)  # Находит позицию
print(index)  # 3

# 2. Поиск в отсортированном списке
# 3. Поиск первого элемента >= target
# 4. Поиск последнего элемента <= target

Таблица сложностей

Оптимизация кода

# ❌ Медленнее: может быть переполнение при больших числах
mid = (left + right) // 2

# ✅ Быстрее и безопаснее
mid = left + (right - left) // 2

Итоги

• O(log n) временная сложность — экспоненциально лучше, чем O(n)
• O(1) пространственная сложность (для итеративной версии)
• Требование: массив должен быть отсортирован
• Идеален для больших наборов данных — даже для 1 млрд элементов нужно только 30 операций