Под отсортированной матрицей будем понимать такую матрицу, строки и столбцы которой отсортированы.

Чтобы найти нужный элемент, можно воспользоваться бинарным поиском по каждой строке. Алгоритм потребует O(M log(N)) времени, так как необходимо обработать М столбцов, на каждый из которых тратится O(log(N)) времени. Также можно обойтись и без сложного бинарного поиска. Мы разберем два метода.

Решение 1: обычный поиск

Прежде чем приступать к разработке алгоритма, давайте рассмотрим простой пример:

 

Допустим, мы ищем элемент 55. Как его найти?

Если мы посмотрим на первые элементы строки и столбца, то можем начать искать расположение искомого элемента. Очевидно, что 55 не может находиться в столбце, который начинается со значения больше 55, так как в начале столбца всегда находится минимальный элемент. Также мы знаем, что 55 не может находиться правее, так как значение первого элемента каждого столбца увеличивается слева направо. Поэтому, если мы обнаружили, что первый элемент столбца больше х, нужно двигаться влево.

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

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

Давайте используем все эти наблюдения для построения решения:

— Если первый элемент столбца больше х, то х находится в колонке слева.
— Если последний элемент столбца меньше х, то х находится в колонке справа.
— Если первый элемент строки больше х, то х находится в строке, расположенной выше.
— Если последний элемент строки меньше х, то х находится в строке, расположенной ниже.

Давайте начнем со столбцов.

Мы должны начать с правого столбца и двигаться влево. Это означает, что первым элементом для сравнения будет [0][с-1], где с — количество столбцов. Сравнивая первый элемент столбца с х (в нашем случае 55), легко понять, что х может находиться в столбцах 0,1 или 2. Давайте начнем с [0][2].

Данный элемент может не являться последним элементом строки в полной матрице, но это конец строки в подматрице. А подматрица подчиняется тем же условиям. Элемент [0][2] имеет значение 40, то есть он меньше, чем наш элемент, а значит, мы знаем, что нам нужно двигаться вниз.

Теперь подматрица принимает следующий вид (серые ячейки отброшены):

Мы можем раз за разом использовать наши правила поиска. Обратите внимание, что мы используем правила 1 и 4.

Следующий код реализует этот алгоритм:

Другой подход к решению задачи — бинарный поиск. Мы получим более сложный код, но построен он будет на тех же правилах.

Решение 2: бинарный поиск

Давайте еще раз обратимся к нашему примеру:

Мы хотим повысить эффективность алгоритма. Давайте зададимся вопросом: где может находиться элемент?

Нам сказано, что все строки и столбцы отсортированы. Это означает, что элемент [i][j] больше, чем элементы в строке i, находящиеся между столбцами 0 и j и элементы в строке j между строками 0 и i-1.
Другими словами:

a[i][0] <= a[i][1] <= … <= a[i][j-i] <= a[i][j]
a[0][j] <= a[1][j] <= … <= a[i-1][j] <= a[i][j]

Посмотрите на матрицу: элемент, который находится в темно-серой ячейке, больше, чем другие выделенные элементы.

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

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

Аналогично, верхний левый угол всегда будет наименьшим. Цвета в приведенной ниже схеме отражают информацию об упорядочивании элементов (светло-серый < белый < темно-серый):

Давайте вернемся к исходной задаче. Допустим, что нам нужно найти элемент 85. Если мы посмотрим на диагональ, то увидим элементы 35 и 95. Какую информацию о местонахождении элемента 85 можно из этого извлечь?

85 не может находиться в темно-серой области, так как элемент 95 расположен в верхнем левом углу и является наименьшим элементом в этом квадрате.

85 не может принадлежать светло-серой области, так как элемент 35 находится в нижнем правом углу.

85 должен быть в одной из двух белых областей.

Таким образом, мы делим нашу сетку на четыре квадранта и выполняем поиск в нижнем левом и верхнем правом квадрантах. Их также можно разбить на квадранты и продолжить поиск.

Обратите внимание, что диагональ отсортирована, а значит, мы можем эффективно использовать бинарный поиск.

Приведенный ниже код реализует этот алгоритм:

Этот код довольно трудно написать правильно с первого раза.