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

Задача:

Задана отсортированная двумерная матрица, состоящая из 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]. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.

Существует еще один способ оптимизации. Рассмотрим случай, когда используется двоичный поиск по строке. Достаточно очевидно, что искомое число может находится только в тех строках, где первый элемент меньше искомого, а последний - больше. Перед началом поиска можно исключить 2 прямоугольных участка матрицы: первый состоит из строк, у которых последний элемент меньше искомого; второй состоит из строк, у которых первый элемент больше искомого. Используя двоичный поиск, можно найти границы этих участков за [math]O(log(n))[/math] для столбцов и за [math]O(log(m))[/math] строк.

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

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

Код

 if (target < a[0][0] || target > a[N-1][N-1]) 
   return false
 row = 0
 col = N-1
   while (row <= N-1 && col >= 0) 
     if (a[row][col] < target) 
       row++
     else if (a[row][col] > target)
       col--
     else
       return true
 return false

Пример поиска числа 13 в матрице

Оценка времени работы

Очевидно, что во время работы указатель сдвигается максимум на n строк и m столбцов. В этом случае время работы составляет [math]O(n + m)[/math].