Бинарный поиск

Бинарный поиск: полный разбор

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

Решение 1: Итеративный подход ⭐ РЕКОМЕНДУЕТСЯ

def binary_search(arr: list[int], target: int) -> int:
    """
    Бинарный поиск в отсортированном массиве.
    
    Алгоритм:
    1. Устанавливаем левую границу (left) и правую границу (right)
    2. Пока left <= right:
       - Вычисляем средний индекс (mid)
       - Если arr[mid] == target, возвращаем индекс
       - Если arr[mid] < target, сужаем область справа (left = mid + 1)
       - Если arr[mid] > target, сужаем область слева (right = mid - 1)
    3. Если элемент не найден, возвращаем -1
    
    Сложность: O(log n) время, O(1) память
    
    Args:
        arr: Отсортированный массив целых чисел
        target: Искомый элемент
    
    Returns:
        Индекс элемента или -1, если не найден
    """
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        # Вычисляем средний индекс (избегаем переполнения)
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid  # Нашли!
        elif arr[mid] < target:
            left = mid + 1  # Ищем в правой половине
        else:
            right = mid - 1  # Ищем в левой половине
    
    return -1  # Не найден

# Примеры
print(binary_search([1, 2, 3, 4, 5, 6, 7], 4))  # 3
print(binary_search([1, 2, 3, 4, 5], 6))  # -1
print(binary_search([1, 3, 5, 7, 9], 7))  # 3
print(binary_search([2], 2))  # 0
print(binary_search([1, 2], 1))  # 0

Решение 2: Рекурсивный подход

def binary_search_recursive(arr: list[int], target: int, left: int = 0, right: int = None) -> int:
    """
    Бинарный поиск рекурсивно.
    
    Сложность: O(log n) время, O(log n) память (стек вызовов)
    """
    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)

# Примеры
print(binary_search_recursive([1, 2, 3, 4, 5, 6, 7], 4))  # 3
print(binary_search_recursive([1, 2, 3, 4, 5], 6))  # -1

Решение 3: Используя встроенный модуль bisect

import bisect

def binary_search_builtin(arr: list[int], target: int) -> int:
    """
    Использует встроенный модуль bisect для бинарного поиска.
    
    Примечание: bisect.bisect_left() возвращает позицию вставки
    """
    index = bisect.bisect_left(arr, target)
    
    # Проверяем, найден ли элемент
    if index < len(arr) and arr[index] == target:
        return index
    return -1

# Примеры
print(binary_search_builtin([1, 2, 3, 4, 5, 6, 7], 4))  # 3
print(binary_search_builtin([1, 2, 3, 4, 5], 6))  # -1

Решение 4: С типизацией и документацией

from typing import List, Optional

def binary_search_typed(arr: List[int], target: int) -> int:
    """
    Бинарный поиск в отсортированном массиве.
    
    Требует:
    - Массив отсортирован в возрастающем порядке
    - Может содержать дубликаты
    
    Args:
        arr: Отсортированный массив
        target: Элемент для поиска
    
    Returns:
        Индекс найденного элемента или -1
    
    Raises:
        TypeError: Если arr не список или target не число
    
    Examples:
        >>> binary_search_typed([1, 2, 3, 4, 5], 3)
        2
        >>> binary_search_typed([1, 2, 3, 4, 5], 6)
        -1
    """
    if not isinstance(arr, list):
        raise TypeError(f"Expected list, got {type(arr).__name__}")
    if not isinstance(target, int):
        raise TypeError(f"Expected int, got {type(target).__name__}")
    
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Тестирование
print(binary_search_typed([1, 2, 3, 4, 5], 3))  # 2

Решение 5: Поиск первого и последнего вхождения

def binary_search_first(arr: list[int], target: int) -> int:
    """
    Находит ПЕРВОЕ вхождение элемента в массив.
    Полезно, когда есть дубликаты.
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid  # Сохраняем результат
            right = mid - 1  # Ищем ещё левее
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

def binary_search_last(arr: list[int], target: int) -> int:
    """
    Находит ПОСЛЕДНЕЕ вхождение элемента в массив.
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid  # Сохраняем результат
            left = mid + 1  # Ищем ещё правее
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

# Примеры с дубликатами
arr = [1, 2, 2, 2, 3, 4, 5]
print(binary_search_first(arr, 2))   # 1 (первое вхождение)
print(binary_search_last(arr, 2))    # 3 (последнее вхождение)
print(binary_search_first(arr, 2))   # 1
print(binary_search_first(arr, 6))   # -1

Решение 6: Поиск позиции вставки

def binary_search_insert_position(arr: list[int], target: int) -> int:
    """
    Возвращает позицию, где должен быть вставлен элемент
    для сохранения отсортированного порядка.
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

# Примеры
print(binary_search_insert_position([1, 3, 5, 6], 5))  # 2
print(binary_search_insert_position([1, 3, 5, 6], 4))  # 2
print(binary_search_insert_position([1, 3, 5, 6], 7))  # 4
print(binary_search_insert_position([1, 3, 5, 6], 0))  # 0

Тестирование

def test_binary_search():
    """
    Comprehensive тестирование бинарного поиска.
    """
    # Базовые случаи
    assert binary_search([1, 2, 3, 4, 5, 6, 7], 4) == 3
    assert binary_search([1, 2, 3, 4, 5], 6) == -1
    assert binary_search([1], 1) == 0
    assert binary_search([1], 2) == -1
    
    # Граничные случаи
    assert binary_search([1, 2, 3, 4, 5], 1) == 0  # Первый элемент
    assert binary_search([1, 2, 3, 4, 5], 5) == 4  # Последний элемент
    
    # Пустой массив
    assert binary_search([], 1) == -1
    
    # Большой массив
    big_arr = list(range(0, 1000, 2))  # [0, 2, 4, ..., 998]
    assert binary_search(big_arr, 500) == 250
    assert binary_search(big_arr, 501) == -1
    
    # С дубликатами
    arr_with_dupes = [1, 2, 2, 2, 3, 4, 5]
    # binary_search вернёт индекс одного из 2, не обязательно первого
    index = binary_search(arr_with_dupes, 2)
    assert 1 <= index <= 3 and arr_with_dupes[index] == 2
    
    # Проверяем первое и последнее вхождение
    assert binary_search_first(arr_with_dupes, 2) == 1
    assert binary_search_last(arr_with_dupes, 2) == 3
    
    print("✓ Все тесты пройдены!")

test_binary_search()

Отладка: правильный расчёт mid

# ПЛОХО: может произойти переполнение в других языках
mid = (left + right) // 2

# ХОРОШО: безопаснее
mid = left + (right - left) // 2

# Пример переполнения (в Python не происходит, но хорошая привычка):
# left = 2^30, right = 2^30 + 1
# left + right может переполниться в языках с ограниченным int
# left + (right - left) // 2 всегда безопасно

Сложность алгоритмов

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

import time

def benchmark_search():
    # Массив из 1 млн элементов
    arr = list(range(1000000))
    target = 500000
    
    # Бинарный поиск
    start = time.time()
    for _ in range(10000):
        binary_search(arr, target)
    time_binary = time.time() - start
    
    # Линейный поиск
    start = time.time()
    for _ in range(100):  # Меньше итераций, т.к. медленнее
        arr.index(target)
    time_linear = time.time() - start
    
    print(f"Бинарный поиск (10k итераций): {time_binary:.4f}с")
    print(f"Линейный поиск (100 итераций): {time_linear:.4f}с")
    # Бинарный поиск быстрее в ~1000 раз

benchmark_search()

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

# 1. Поиск минимального элемента >= target
def find_ceiling(arr: list[int], target: int) -> int:
    """Найти минимальный элемент >= target"""
    left, right = 0, len(arr) - 1
    result = float('inf')
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:
            result = min(result, arr[mid])
            right = mid - 1
        else:
            left = mid + 1
    
    return result if result != float('inf') else -1

# 2. Поиск максимального элемента <= target
def find_floor(arr: list[int], target: int) -> int:
    """Найти максимальный элемент <= target"""
    left, right = 0, len(arr) - 1
    result = float('-inf')
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            result = max(result, arr[mid])
            left = mid + 1
        else:
            right = mid - 1
    
    return result if result != float('-inf') else -1

print(find_ceiling([1, 5, 10, 20], 6))  # 10
print(find_floor([1, 5, 10, 20], 6))     # 5

Итоговое решение для production

def binary_search(arr: list[int], target: int) -> int:
    """
    Бинарный поиск в отсортированном массиве.
    
    Сложность: O(log n) время, O(1) память
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Ключевые моменты:
# 1. mid = left + (right - left) // 2 (безопаснее)
# 2. while left <= right (условие правильное)
# 3. Возвращаем -1, если не найдено
# 4. O(log n) вместо O(n) - колоссальное ускорение