748
правок
Изменения
Новая страница: «{{Задача |definition = Дана матрица, в которой отсортированы все столбцы и строки. Требуется на...»
{{Задача
|definition = Дана матрица, в которой отсортированы все столбцы и строки. Требуется найти заданный элемент <tex>x</tex>.}}
== Варианты решения ==
=== Наивное решение ===
==== Описание алгоритма ====
Нам известно:
* Если первый элемент столбца больше <tex>x</tex>, то <tex>x</tex> находится в колонке слева.
* Если последний элемент столбца меньше <tex>x</tex>, то <tex>x</tex> находится в колонке справа.
* Если первый элемент строки больше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной выше.
* Если последний элемент строки меньше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной ниже.
|definition = Дана матрица, в которой отсортированы все столбцы и строки. Требуется найти заданный элемент <tex>x</tex>.}}
== Варианты решения ==
=== Наивное решение ===
==== Описание алгоритма ====
Нам известно:
* Если первый элемент столбца больше <tex>x</tex>, то <tex>x</tex> находится в колонке слева.
* Если последний элемент столбца меньше <tex>x</tex>, то <tex>x</tex> находится в колонке справа.
* Если первый элемент строки больше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной выше.
* Если последний элемент строки меньше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной ниже.
