54
правки
Изменения
Нет описания правки
{{Определение
|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>log(m)) ==
Данный способ решения использует наивное решение за <math>n \cdot m</math>, улучшенное с помощью [[Целочисленный двоичный поиск|двоичного поиска]]. Для этого в каждой строке запускается двоичный поиск. Время работы — <tex>O(n \cdot log(m))</tex>.
'''Замечание'''
Время работы может быть улучшено до <tex>O(min(n, m) \cdot log(max(n \cdot m))</tex>. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.
Существует еще один способ оптимизации. Рассмотрим случай, когда используется двоичный поиск по строке. Достаточно очевидно, что искомое число может находится только в тех строках, где первый элемент меньше искомого, а последний - — больше. Перед началом поиска можно исключить 2 прямоугольных участка матрицы: первый состоит из строк, у которых последний элемент меньше искомого; второй состоит из строк, у которых первый элемент больше искомого. Используя двоичный поиск, можно найти границы этих участков за <tex>O(log(n))</tex> для столбцов и за <tex>O(log(m))</tex> строк.
== Решение за O(n + m) ==
