Изменения

|definition = Задана отсортированная двумерная матрица (матрица, для которой выполнено следующее условие: <tex> a[row][col] \le a[row + 1][col], a[row][col] \le 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> строк. 

Существует еще один способ оптимизации[[Файл:find13. Рассмотрим случай, когда используется двоичный поиск по строке. Достаточно очевидно, что искомое число может находится только png|320px|thumb|right|Пример поиска числа 13 в тех строках, где первый элемент меньше искомого, а последний — больше. Перед началом поиска можно исключить 2 прямоугольных участка матрицы: первый состоит из строк, у которых последний элемент меньше искомого; второй состоит из строк, у которых первый элемент больше искомого. Используя двоичный поиск, можно найти границы этих участков за <tex>O(log(n))</tex> для столбцов и за <tex>O(log(m))</tex> строк.матрице]]

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

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

'''return''' true(row, col) '''return''' ''' false'''