Минимальное и максимальное в массиве

Решение

Анализ задачи

Необходимо найти минимальный и максимальный элементы в массиве за один проход. Это классическая задача оптимизации, которая проверяет эффективность алгоритма и понимание временной сложности. Для QA Automation Engineer это важно, так как требует написания оптимизированного кода с предсказуемой производительностью.

Решение

Создам функцию, которая найдёт оба значения за один проход по массиву:

def find_min_max(arr: list) -> tuple[int | float, int | float]:
    """Находит минимальный и максимальный элементы за один проход."""
    if not arr:
        raise ValueError("Массив не может быть пустым")
    
    min_val = max_val = arr[0]
    
    for i in range(1, len(arr)):
        if arr[i] < min_val:
            min_val = arr[i]
        if arr[i] > max_val:
            max_val = arr[i]
    
    return min_val, max_val


class MinMaxFinder:
    """Класс для поиска минимума и максимума в массиве."""
    
    @staticmethod
    def find_optimized(arr: list) -> dict:
        """Оптимизированный поиск с уменьшением количества сравнений."""
        if not arr:
            raise ValueError("Массив не может быть пустым")
        
        if len(arr) == 1:
            return {"min": arr[0], "max": arr[0], "comparisons": 0}
        
        min_val = max_val = None
        comparisons = 0
        
        # Для чётного массива: берём пары элементов
        start = 0
        if len(arr) % 2 == 1:
            min_val = max_val = arr[0]
            start = 1
        
        # Сравниваем элементы попарно для уменьшения количества операций
        for i in range(start, len(arr), 2):
            if i + 1 < len(arr):
                if arr[i] < arr[i + 1]:
                    smaller, larger = arr[i], arr[i + 1]
                else:
                    smaller, larger = arr[i + 1], arr[i]
                
                if min_val is None:
                    min_val = smaller
                    max_val = larger
                else:
                    if smaller < min_val:
                        min_val = smaller
                    if larger > max_val:
                        max_val = larger
                
                comparisons += 3  # 1 сравнение пары + 2 для min/max
            else:
                if min_val is None or arr[i] < min_val:
                    min_val = arr[i]
                if max_val is None or arr[i] > max_val:
                    max_val = arr[i]
                comparisons += 2
        
        return {"min": min_val, "max": max_val, "comparisons": comparisons}

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

# Простой вариант
min_val, max_val = find_min_max([3, 5, 1, 8, 2])
print(f"min = {min_val}, max = {max_val}")  # min = 1, max = 8

# Оптимизированный вариант с подсчётом сравнений
result = MinMaxFinder.find_optimized([3, 5, 1, 8, 2])
print(f"min = {result["min"]}, max = {result["max"]}")
print(f"Количество сравнений: {result["comparisons"]}")

# Граничные случаи
print(find_min_max([42]))              # (42, 42)
print(find_min_max([5, 3, 9, 1]))      # (1, 9)
print(find_min_max([-10, -5, -20]))    # (-20, -5)

Ключевые моменты

Основной подход:

• Временная сложность: O(n) — один проход
• Пространственная сложность: O(1) — только две переменные
• На каждом шаге выполняются ровно два сравнения

Оптимизированный подход:

• Уменьшает количество сравнений с 2n до 1.5n
• Сравнивает элементы попарно перед сравнением с текущими min/max
• Критично для больших массивов

Для автоматизации тестирования:

• Проверка пустого массива (обработка ошибок)
• Массивы с одним элементом
• Отрицательные числа
• Дублирующиеся значения
• Уже отсортированные массивы