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

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

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

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

15	20	40	85
20	35	80	95
30	55	95	105
40	80	100	120

Допустим, мы ищем элемент 55. Как его найти?
Если мы посмотрим на первые элементы строки и столбца, то можем начать искать расположение искомого элемента. Очевидно, что 55 не может находиться в столбце, который начинается со значения больше 55, так как в начале столбца всегда находится минимальный элемент. Также мы знаем, что 55 не может находиться правее, так как значение первого элемента каждого столбца увеличивается слева направо. Поэтому, если мы обнаружили, что первый элемент столбца больше х, нужно двигаться влево.
Аналогичную проверку можно использовать и для строк. Если мы начали со строки, значение первого элемента которой больше х, нужно двигаться вверх.
Аналогичные рассуждения можно использовать и при анализе последних элементов столбцов или строк. Если последний элемент столбца или строки меньше х, то, чтобы найти х, нужно двигаться вниз (для строк) или направо (для столбцов). Это так, поскольку последний элемент всегда будет максимальным.
Давайте используем все эти наблюдения для построения решения:

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

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

15	20	40	85
20	35	80	95
30	55	95	105
40	80	100	120

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