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

Задача:

Задана отсортированная двумерная матрица, состоящая из n строк и m столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.

Определение:

Отсортированная матрица - матрица, для которой выполнено следующее условие: [math] a[row][col] \le a[row + 1][col], a[row][col] \le a[row][col + 1] [/math]

Решение за O(n[math]\cdot[/math]m)

Для начала рассмотрим наивный алгоритм поиска элемента. В каждой строке исходной матрицы запускаем линейный поиск, если находим элемент, то возвращаем его координаты [math](row, col)[/math]. Время работы — [math]O(n \cdot m)[/math].

Решение за O(n[math]\cdot[/math]log(m))

Данный способ решения использует наивное решение за [math]n \cdot m[/math], улучшенное с помощью двоичного поиска. Для этого в каждой строке запускается двоичный поиск. Время работы — [math]O(n \cdot log(m)[/math].

Замечание

Время работы может быть улучшено до [math]O(min(n, m) \cdot log(max(n \cdot m))[/math]. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.

Решение за O(n + m)

В данном решении мы начинаем поиск из правого верхнего угла и движемся к искомому элементу. Идея алгоритма в том, что если текущий элемент меньше необходимого, то мы сдвигаемся на одну строку вниз. Если он больше, то мы сдвигаемся на одну колонку вправо.