Что такое бинарный поиск и как он работает?

Бинарный поиск (Binary Search)

Бинарный поиск — один из самых эффективных алгоритмов поиска элемента в отсортированном массиве. Он использует принцип "разделяй и властвуй".

Как это работает

Вместо того чтобы проверять каждый элемент (линейный поиск, O(n)), бинарный поиск делит массив пополам и исключает половину вариантов на каждой итерации:

def binary_search(arr, target):
    """
    Поиск элемента в отсортированном массиве.
    
    Args:
        arr: Отсортированный список
        target: Искомый элемент
    
    Returns:
        Индекс элемента или -1 если не найден
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        # Находим середину (более безопасно чем (left + right) // 2)
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid  # Нашли!
        elif arr[mid] < target:
            # target справа, исключаем левую половину
            left = mid + 1
        else:
            # target слева, исключаем правую половину
            right = mid - 1
    
    return -1  # Не найдено

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

Пошаговый пример

Допустим ищем 7 в массиве [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]:

Шаг 1: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
       left=0        mid=4        right=9
       arr[4] = 9 > 7, ищем слева

Шаг 2: [1, 3, 5, 7, 9]
       left=0   mid=2   right=3
       arr[2] = 5 < 7, ищем справа

Шаг 3: [7, 9]
            mid=3
            arr[3] = 7 ✅ Найдено!

Сложность

• Временная сложность: O(log n) — огромное преимущество
• Пространственная сложность: O(1) для итеративного, O(log n) для рекурсивного

Сравнение:

import time
import random

arr = sorted([random.randint(1, 1_000_000) for _ in range(1_000_000)])
target = arr[500_000]

# Линейный поиск
start = time.time()
for i, x in enumerate(arr):
    if x == target:
        break
print(f"Linear search: {time.time() - start:.4f}s")  # ~0.01-0.02s

# Бинарный поиск
start = time.time()
binary_search(arr, target)
print(f"Binary search: {time.time() - start:.6f}s")  # ~0.0001s (в 100 раз быстрее!)

Рекурсивная реализация

def binary_search_recursive(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1
    
    mid = left + (right - left) // 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)

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

1. Поиск в больших наборах данных

# Найти первого пользователя с ID >= 1000
users = sorted(users, key=lambda u: u.id)
idx = binary_search(users_ids, 1000)

2. Поиск границы (bisect в Python)

Python имеет встроенный модуль bisect:

import bisect

arr = [1, 3, 5, 7, 9]

# Найти позицию для вставки, чтобы сохранить сортировку
pos = bisect.bisect_left(arr, 5)   # Вернёт 2
pos = bisect.bisect_right(arr, 5)  # Вернёт 3

# Или используй встроенный поиск
arr.sort()
from bisect import bisect_left
idx = bisect_left(arr, 5)

3. Поиск в матрице

def search_matrix(matrix, target):
    """Поиск в отсортированной матрице"""
    if not matrix or not matrix[0]:
        return False
    
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        mid_value = matrix[mid // n][mid % n]  # Преобразуем в 2D
        
        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

ВАЖНОЕ: Требование отсортированности!

Бинарный поиск работает только для отсортированных массивов:

# ❌ Неправильно — массив не отсортирован
arr = [5, 1, 3, 7, 9]
binary_search(arr, 3)  # Может вернуть -1 (неправильно!)

# ✅ Правильно
arr = sorted(arr)
binary_search(arr, 3)  # Вернёт 1

Когда использовать

• Поиск в больших отсортированных списках ✅
• Поиск в неотсортированных данных — используй hash table ❌
• Очень часто ищете? Используй индекс/B-tree (БД) ✅

Итог

Бинарный поиск — фундаментальный алгоритм:

• O(log n) сложность делает его невероятно быстрым
• Требует отсортированного массива
• Основа для многих структур данных (B-trees, skip lists)
• Практическое применение: БД индексы, API пагинация, игровой рейтинг