Поиск в отсортированной матрице

Решение: Поиск в отсортированной матрице

Описание проблемы

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

Оптимальный алгоритм: Начало с угла

Лучший подход — начать поиск с одного из углов матрицы (обычно верхний правый или нижний левый). Это использует свойство отсортированности как по строкам, так и по столбцам.

Стратегия:

1. Начните с верхнего правого элемента (позиция [0, N-1])
2. Если текущий элемент равен цели — найдено
3. Если текущий элемент больше цели — двигайтесь влево (столбец уменьшается)
4. Если текущий элемент меньше цели — двигайтесь вниз (строка увеличивается)
5. Повторяйте, пока не найдёте элемент или не выйдете за границы матрицы

Реализация на Python

def search_matrix(matrix, target):
    """
    Поиск элемента в отсортированной матрице.
    
    Args:
        matrix: List[List[int]] - матрица с отсортированными строками и столбцами
        target: int - искомый элемент
    
    Returns:
        tuple: (found: bool, position: (row, col) или None)
    """
    if not matrix or not matrix[0]:
        return False, None
    
    rows = len(matrix)
    cols = len(matrix[0])
    
    # Начинаем с верхнего правого угла
    row = 0
    col = cols - 1
    
    while row < rows and col >= 0:
        current = matrix[row][col]
        
        if current == target:
            return True, (row, col)
        elif current > target:
            col -= 1  # Двигаемся влево
        else:
            row += 1  # Двигаемся вниз
    
    return False, None

Тестовый пример

matrix = [
    [1, 4, 7, 11],
    [2, 5, 8, 12],
    [3, 6, 9, 16],
    [10, 13, 14, 17]
]

found, pos = search_matrix(matrix, 5)
print(f"Найдено: {found}, Позиция: {pos}")  # Найдено: True, Позиция: (1, 1)
print(search_matrix(matrix, 20))  # (False, None)

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

• Временная сложность: O(M + N) — худший случай: идём от верхнего правого угла до нижнего левого
• Пространственная сложность: O(1) — используем только константное количество переменных

Почему этот подход работает

Ключевое свойство: от верхнего правого угла все элементы влево меньше, все элементы внизу больше. Это позволяет исключать строки и столбцы на каждом шаге, как в бинарном поиске.

Альтернативные подходы

Бинарный поиск по диагонали — сложнее в реализации, но также O(log(M*N)) в некоторых случаях. Для этой задачи метод угла предпочтительнее благодаря простоте и эффективности.

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

Этот алгоритм полезен при тестировании:

• Поиска элементов в таблицах с отсортированными данными
• Оптимизации поиска в больших наборах данных
• Валидации корректности сортировки в API ответах