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