54
правки
Изменения
→Код
{{Задача
|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> столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.
}}
[[Файл:sorted_matrix_example.png|320px|thumb|right|Пример отсортированной матрицы]]
== Решение за 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>. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот. Существует еще один способ оптимизации. Рассмотрим случай, когда используется двоичный поиск по строке. Достаточно очевидно, что искомое число может находится только в тех строках, где первый элемент меньше искомого, а последний — больше. Перед началом поиска можно исключить два прямоугольных участка матрицы: первый состоит из строк, у которых последний элемент меньше искомого; второй состоит из строк, у которых первый элемент больше искомого. Используя двоичный поиск, можно найти границы этих участков за <tex>O(\log(n))</tex> для столбцов и за <tex>O(\log(m))</tex> строк.
== Решение за O(n + m) ==
В данном решении мы начинаем поиск из правого верхнего угла и движемся к искомому элементу. Идея алгоритма в том, что если текущий элемент меньше необходимого, то мы сдвигаемся на одну строку вниз. Если он больше, то мы сдвигаемся на одну колонку вправовлево. === Доказательство корректности ===
Докажем, что каждый ход в соседнюю ячейку отсекает только те столбцы или строки, которые точно не содержат искомый элемент. Назовем ход корректным, если он отсекает только те строки или колонки, в которых точно нет искомого элемента. Пусть первый ход (в правую верхнюю ячейку) корректный (он не отсек ни одной строки или столбца).
=== Код ===
'''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)
'''if''' (a[row][col] < target)
row++
col--
'''else'''
'''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]