54
правки
Изменения
Нет описания правки
{{Задача
|definition = Задана отсортированная двумерная матрица, состоящая из n строк и m столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.
}}
{{Определение
|id=def1
|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>.
