PrepBro
← Назад к вопросам

Почему бинарный поиск отдает логарифм?

1.3 Junior🔥 131 комментариев
#Асинхронность и многопоточность

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Почему бинарный поиск имеет логарифмическую сложность O(log n)

Простой ответ: потому что бинарный поиск каждый раз делит размер пространства поиска пополам, а количество делений пополам до единицы — это логарифм.

Интуитивное объяснение

Пример: поиск числа в отсортированном массиве [1, 2, 3, ..., 1024]

Шаг 1: смотрим середину (512)
       размер: 1024 -> 512

Шаг 2: смотрим середину половины (256)
       размер: 512 -> 256

Шаг 3: смотрим середину четверти (128)
       размер: 256 -> 128

Шаг 4: размер: 128 -> 64
Шаг 5: размер: 64 -> 32
Шаг 6: размер: 32 -> 16
Шаг 7: размер: 16 -> 8
Шаг 8: размер: 8 -> 4
Шаг 9: размер: 4 -> 2
Шаг 10: размер: 2 -> 1 (нашли!)

Всего шагов: 10
log2(1024) = 10

Математическое доказательство

Рекурсивное отношение:

T(n) = T(n/2) + 1  (один шаг сравнения + рекурсия на половине массива)

Разворачиваем:
T(n) = T(n/2) + 1
     = T(n/4) + 1 + 1
     = T(n/8) + 1 + 1 + 1
     = T(n/16) + 1 + 1 + 1 + 1
     ...

Когда n/2^k = 1 (т.е. нашли элемент):
n = 2^k
k = log2(n)

Общее количество шагов = k = log2(n)

Прямое сравнение: линейный vs логарифмический поиск

import math

# Размер массива vs количество операций
sizes = [10, 100, 1000, 10_000, 100_000, 1_000_000]

for n in sizes:
    linear = n                 # O(n) — линейный поиск
    binary = math.log2(n)      # O(log n) — бинарный поиск
    speedup = linear / binary
    
    print(f"n={n:,}")
    print(f"  Линейный:     {linear:,} операций")
    print(f"  Бинарный:     {binary:.1f} операций")
    print(f"  Ускорение:    {speedup:.0f}x раз")
    print()

# Output:
# n=10
#   Линейный:     10 операций
#   Бинарный:     3.3 операций
#   Ускорение:    3x раз
#
# n=1,000,000
#   Линейный:     1,000,000 операций
#   Бинарный:     20.0 операций
#   Ускорение:    50,000x раз

Реальная реализация бинарного поиска

def binary_search(arr: list, target: int) -> int:
    """
    Поиск target в отсортированном массиве arr
    Возвращает индекс или -1 если не найдено
    """
    left, right = 0, len(arr) - 1
    iterations = 0
    
    while left <= right:
        iterations += 1
        mid = (left + right) // 2
        
        print(f"Итерация {iterations}: смотрим arr[{mid}] = {arr[mid]}")
        
        if arr[mid] == target:
            print(f"Найдено за {iterations} итераций")
            return mid
        elif arr[mid] < target:
            left = mid + 1   # Ищем в правой половине
        else:
            right = mid - 1  # Ищем в левой половине
    
    return -1

# Пример
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
result = binary_search(arr, 13)

# Output:
# Итерация 1: смотрим arr[4] = 9
# Итерация 2: смотрим arr[7] = 15
# Итерация 3: смотрим arr[6] = 13
# Найдено за 3 итерации
# log2(10) ≈ 3.3

Визуализация сокращения пространства поиска

Массив: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
Ищем: 13

Итерация 1:
[1, 2, 3, 4, 5, 6, 7, 8, | 9, 10, 11, 12, 13, 14, 15, 16]
              ↑                    середина = 8
8 < 13, ищем справа
Размер: 16 -> 8

Итерация 2:
[9, 10, 11, 12, | 13, 14, 15, 16]
          ↑              середина = 12
12 < 13, ищем справа
Размер: 8 -> 4

Итерация 3:
[13, 14, | 15, 16]
  ↑            середина = 14
14 > 13, ищем слева
Размер: 4 -> 2

Итерация 4:
[13, 14]
↑        середина = 13
Найдено!
Размер: 2 -> 1

Всего итераций: 4
log2(16) = 4 ✓

Формула логарифма в контексте бинарного поиска

# Максимальное количество сравнений в бинарном поиске:
# k = log2(n) (округлено вверх)

import math

def max_iterations(array_size: int) -> int:
    """Максимальное количество итераций бинарного поиска"""
    return math.ceil(math.log2(array_size + 1))

for size in [1, 2, 4, 8, 16, 32, 64, 128, 256, 1024]:
    max_iters = max_iterations(size)
    print(f"Размер: {size:4d} -> Макс итераций: {max_iters}")

# Output:
# Размер:    1 -> Макс итераций: 1
# Размер:    2 -> Макс итераций: 2
# Размер:    4 -> Макс итераций: 3
# Размер:    8 -> Макс итераций: 4
# Размер:   16 -> Макс итераций: 5
# Размер:   32 -> Макс итераций: 6
# Размер:   64 -> Макс итераций: 7
# Размер:  128 -> Макс итераций: 8
# Размер:  256 -> Макс итераций: 9
# Размер: 1024 -> Макс итераций: 11

Сравнение сложностей

import math

def compare_algorithms(n: int):
    print(f"Для массива размером {n:,}:")
    print(f"  O(1)      (константа):       {1:,} операций")
    print(f"  O(log n)  (бинарный поиск):  {int(math.log2(n)):,} операций")
    print(f"  O(n)      (линейный поиск):  {n:,} операций")
    print(f"  O(n²)     (пузырьковая сор): {n*n:,} операций")
    print()

for size in [10, 100, 1000, 10_000, 100_000, 1_000_000]:
    compare_algorithms(size)

Почему это логарифм, а не что-то другое?

Ключ в делении пополам:

Линейный поиск: 1, 2, 3, 4, 5, ..., n
Операции: n

Бинарный поиск: n -> n/2 -> n/4 -> n/8 -> ... -> 1
Операции: log₂(n)

Вопрос: сколько раз нужно поделить n на 2, чтобы получить 1?
Ответ: log₂(n) раз

Математически:
n / 2^k = 1
2^k = n
k = log₂(n)

Практическое значение

# Для одного миллиона элементов:
print(f"Линейный поиск:  1,000,000 сравнений (в худшем случае)")
print(f"Бинарный поиск:  {math.ceil(math.log2(1_000_000))} сравнений")
print(f"Ускорение:       {1_000_000 / math.log2(1_000_000):.0f}x раз")

# Output:
# Линейный поиск:  1,000,000 сравнений (в худшем случае)
# Бинарный поиск:  20 сравнений
# Ускорение:       50000x раз

Условие: массив должен быть отсортирован

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

sorted_arr = [1, 3, 5, 7, 9, 11, 13]
unsorted_arr = [3, 7, 1, 5, 13, 9, 11]

# Правильно
binary_search(sorted_arr, 13)      # O(log n) ✓

# Неправильно
binary_search(unsorted_arr, 13)    # Может не найти! ✗

# Нужно сортировать сначала: O(n log n)
sorted_arr = sorted(unsorted_arr)  # O(n log n)
binary_search(sorted_arr, 13)      # O(log n)

Вывод

Бинарный поиск имеет O(log n) потому что:

  1. Каждый шаг делит пространство поиска пополам
  2. Логарифм отвечает на вопрос: сколько раз нужно поделить n на 2, чтобы получить 1?
  3. Ответ: k = log₂(n) раз
  4. Практически: для 1 млн элементов нужно максимум 20 сравнений

Это один из самых элегантных примеров, как правильный алгоритм может дать экспоненциальное ускорение.