54
правки
Изменения
Нет описания правки
{{Задача
|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> столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.
}}
Пусть предыдущий ход был корректным. Докажем, что следующий ход, выполненный по правилам, будет корректным.
Если текущий элемент меньше искомого, то очевидно, что все ячейки левее и выше меньше, чем искомый. Значит(по определению отсортированной матрицы, все элементы левее в строке меньше текущего, их можно отсечьа текущий меньше искомого). Если текущий элемент больше искомого, то очевидно, что все ячейки правее и ниже больше, чем искомый(по определению отсортированной матрицы, все элементы ниже в столбце больше текущего, а текущий больше искомого). Значит, их тоже можно отсечь.
В определенный момент времени алгоритм либо найдет ячейку с искомым элементом (значит, элемент найден), либо в матрице не останется тех элементов, которые не были отсечены (значит, элемента в матрице нет).
=== Код ===
'''intpair''' matrixFind('''int'''[N][M] a, '''int ''' target): '''if''' (target < a[0][0] OR '''or''' target > a[N-1][N-1]) '''return''' '''false'''(-1, -1)
row = 0
col = N-1 '''while''' (row <= N-1 AND '''and''' col >= 0)
'''if''' (a[row][col] < target)
row++
'''else'''
'''return''' (row, col)
'''return''' '''false'''(-1, -1)
