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

Решение: Бинарный поиск

Описание алгоритма

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

Принцип работы:

1. Определяем левый (left) и правый (right) указатели
2. Находим середину: mid = (left + right) // 2
3. Сравниваем элемент в середине с целевым значением
4. Если равны — найдено
5. Если target больше — ищем в правой половине (left = mid + 1)
6. Если target меньше — ищем в левой половине (right = mid - 1)
7. Повторяем, пока left <= right

Реализация: Итеративный подход

def binary_search(arr, target):
    """
    Бинарный поиск элемента в отсортированном массиве (итеративный).
    
    Args:
        arr: List[int] - отсортированный массив
        target: int - искомый элемент
    
    Returns:
        int - индекс элемента или -1 если не найдено
    """
    left = 0
    right = 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  # Элемент не найдена

Реализация: Рекурсивный подход

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)

Примеры использования

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

# Поиск существующего элемента
print(binary_search(arr, 7))   # 3 (индекс элемента 7)
print(binary_search(arr, 1))   # 0
print(binary_search(arr, 13))  # 6

# Поиск несуществующего элемента
print(binary_search(arr, 6))   # -1
print(binary_search(arr, 0))   # -1
print(binary_search(arr, 20))  # -1

# Пустой массив
print(binary_search([], 5))    # -1

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

• Временная сложность: O(log n) — на каждом шаге область поиска сокращается вдвое
• Пространственная сложность:
  • Итеративный: O(1) — константное количество переменных
  • Рекурсивный: O(log n) — стек вызовов глубиной log n

Вариант: Поиск границ

def binary_search_left(arr, target):
    """
    Найти первый индекс элемента (левую границу).
    Полезно когда в массиве дубликаты.
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 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_right(arr, target):
    """
    Найти последний индекс элемента (правую границу).
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Продолжаем искать вправо
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Частые ошибки

1. Переполнение при расчёте mid: используй mid = left + (right - left) // 2 вместо (left + right) // 2
2. Бесконечный цикл: убедись что left и right изменяются корректно
3. Граничные случаи: проверь пустой массив, массив с одним элементом, элемент не найден
4. Индекс вне границ: используй <= в условии цикла

Практическое применение в QA Automation

• Поиск значений в логах (обычно отсортированы по времени)
• Проверка больших датасетов API ответов
• Валидация индексов при работе с таблицами в UI тестах
• Оптимизация производительности скриптов с большими объёмами данных
• Поиск критических значений в мониторинге и алертах