Изменения
→Код
{{Задача
|definition = Задана отсортированная двумерная матрица (матрица, для которой выполнено следующее условие: <tex> a[row][col] \le leqslant a[row + 1][col], a[row][col] \le leqslant a[row][col + 1] </tex> ), состоящая из <tex>n</tex> строк и <tex>m</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> строк.
Пусть предыдущий ход был корректным. Докажем, что следующий ход, выполненный по правилам, будет корректным.
Если текущий элемент меньше искомого, то очевидно, что все ячейки левее и выше меньше, чем искомый. Значит(по определению отсортированной матрицы, все элементы левее в строке меньше текущего, их можно отсечьа текущий меньше искомого). Если текущий элемент больше искомого, то очевидно, что все ячейки правее и ниже больше, чем искомый(по определению отсортированной матрицы, все элементы ниже в столбце больше текущего, а текущий больше искомого). Значит, их тоже можно отсечь.
В определенный момент времени алгоритм либо найдет ячейку с искомым элементом (значит, элемент найден), либо в матрице не останется тех элементов, которые не были отсечены (значит, элемента в матрице нет).
=== Код ===
'''Pair'''<'''int''' , '''int'''> matrixFind('''int'''[N][M] a, '''int ''' target): '''if''' (target < a[0][0] OR '''or''' target > a[N-1][NM-1]) '''return''' '''false'''(-1, -1)
row = 0
col = NM -1 '''while''' (row <= N-1 AND '''and''' col >= 0)
'''if''' (a[row][col] < target)
row++
'''else'''
'''return''' (row, col)
'''return''' '''false'''(-1, -1)
===Оценка времени работы===
Очевидно, что во время работы указатель сдвигается максимум на <tex>n</tex> строк и <tex>m</tex> столбцов. В этом случае время работы составляет <tex>O(n + m)</tex>.
==См. также =Оценка времени работы=* [[Целочисленный_двоичный_поиск|Целочисленный двоичный поиск]] ==Источники информации ==* [http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix.html| Searching a 2D Sorted Matrix часть 1 на Leetcode]* [http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html| Searching a 2D Sorted Matrix часть 2 на Leetcode]
