Изменения

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

}}

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

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

}}

== Решение за O(n<tex>\cdot</tex>m) ==

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

'''if''' (target < a[0][0] || target > a[N-1][N-1])