Изменения

|definition = Задана отсортированная двумерная матрица (матрица, для которой выполнено следующее условие: <tex> a[row][col] \leqslant a[row + 1][col], a[row][col] \leqslant a[row][col + 1] </tex> ), состоящая из <tex>n </tex> строк и <tex>m </tex> столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.

Данный способ решения использует наивное решение за <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> строк.  [[Файл:find13.png|320px|thumb|right|Пример поиска числа 13 в матрице]]

В данном решении мы начинаем поиск из правого верхнего угла и движемся к искомому элементу. Идея алгоритма в том, что если текущий элемент меньше необходимого, то мы сдвигаемся на одну строку вниз. Если он больше, то мы сдвигаемся на одну колонку вправовлево. 

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

'''Pair'''<'''int''', '''int'''> matrixFind('''int'''[N][M] a, '''int''' target): '''if''' (target < a[0][0] || '''or''' target > a[N-1][N-1]) '''return''' false(-1, -1) row = 0 col = N-1 '''while''' (row <= N-1 && '''and''' col >= 0)

'''return''' true(row, col) '''return''' false(-1, -1) ===Оценка времени работы=== Очевидно, что во время работы указатель сдвигается максимум на <tex>n</tex> строк и <tex>m</tex> столбцов. В этом случае время работы составляет <tex>O(n + m)</tex>.

== См. также ==* [[Файл:find13.png|320px|thumb|rightЦелочисленный_двоичный_поиск|Пример поиска числа 13 в матрицеЦелочисленный двоичный поиск]]

===Оценка времени работы=Источники информации ==* [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]

Очевидно, что во время работы указатель сдвигается максимум на n строк [[Категория: Дискретная математика и m столбцов. В этом случае время работы составляет <tex>O(n + m)</tex>.алгоритмы]][[Категория: Алгоритмы поиска]]