Какой принцип действия у алгоритма двоичного поиска?

Принцип действия алгоритма двоичного поиска

Двоичный поиск (binary search) — это фундаментальный алгоритм поиска элемента в отсортированном массиве за логарифмическое время. Это один из самых эффективных алгоритмов в информатике.

Основной принцип

Алгоритм работает по принципу "разделяй и властвуй" — на каждом шаге он делит диапазон поиска пополам и определяет, в какой половине находится искомый элемент.

Пошаговое описание

Шаг 1: Определение границ

left = 0           # Левая граница
right = len(arr) - 1  # Правая граница

Шаг 2: Вычисление середины

mid = (left + right) // 2  # Индекс середины

Шаг 3: Сравнение

if arr[mid] == target:
    return mid  # Элемент найден
elif arr[mid] < target:
    left = mid + 1  # Ищем в правой половине
else:
    right = mid - 1  # Ищем в левой половине

Шаг 4: Повторение

Процесс повторяется, пока не найдем элемент или диапазон не исчерпается.

Полная реализация

def binary_search(arr, target):
    """
    Двоичный поиск в отсортированном массиве.
    
    Args:
        arr: Отсортированный массив
        target: Искомый элемент
    
    Returns:
        Индекс элемента или -1, если не найден
    """
    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  # Элемент не найден

# Пример использования
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 10))  # -1

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

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) // 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)

Встроенные функции Python

В модуле bisect уже реализован двоичный поиск:

import bisect

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

# Найти позицию для вставки
pos = bisect.bisect_left(arr, 7)  # Возвращает 3
pos = bisect.bisect_right(arr, 7)  # Возвращает 4

# Проверить наличие
if arr[pos] == target:
    print(f"Найден на позиции {pos}")
else:
    print("Не найден")

Анализ сложности

Временная сложность:

• Лучший случай: O(1) — элемент в середине
• Средний случай: O(log n)
• Худший случай: O(log n) — максимум n итераций

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

• Итеративная версия: O(1)
• Рекурсивная версия: O(log n) — стек вызовов

Визуализация процесса

Массив: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Ищем: 13

Итерация 1: left=0, right=9, mid=4, arr[4]=9 < 13
  Новые границы: left=5, right=9

Итерация 2: left=5, right=9, mid=7, arr[7]=15 > 13
  Новые границы: left=5, right=6

Итерация 3: left=5, right=6, mid=5, arr[5]=11 < 13
  Новые границы: left=6, right=6

Итерация 4: left=6, right=6, mid=6, arr[6]=13 == 13
  НАЙДЕН! Индекс = 6

Условия применения

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

• Массив отсортирован
• Нет дубликатов (или используется bisect)
• Доступ к элементам за O(1) (массив, не связный список)

Не подходит для:

• Несортированных данных
• Связных списков
• Поиска всех вхождений элемента (используй другой подход)

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

# 1. Поиск диапазона дат
data_points = [(date1, val1), (date2, val2), ...]
# Найти данные за определённый период

# 2. Поиск ближайшего значения
temperatures = [20.1, 20.5, 20.9, 21.2, 21.8]
pos = bisect.bisect_left(temperatures, 20.7)
nearest = temperatures[pos]  # 20.9

# 3. Проверка наличия в большом массиве
import bisect
if bisect.bisect_left(large_arr, target) < len(large_arr):
    if large_arr[bisect.bisect_left(large_arr, target)] == target:
        print("Найден")

Вывод

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