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

Задача:

Задана отсортированная двумерная матрица, состоящая из 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)

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

Код

 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].

Решение за O(log^2(n))

Идея решения за O([math](log(n))^2[/math]) основана на принципе "разделяй и властвуй".

Идея решения

1) Выбираем центральную строку или столбец в матрице (middle), по которому мы будем перемещаться. Используя линейный поиск, необходимо найти такое значение i, что выполняется следующее условие: [math]a[middle][i] \lt target \lt a[middle][i+1][/math].