147
правок
Изменения
Нет описания правки
{{Задача
|definition = Дана матрица, в которой отсортированы все <math>\alpha_k^m</math>. Все столбцы и строкиматрицы отсортированы. Требуется найти заданный элемент <tex>x</tex>.}}
== Варианты решения ==
=== Наивное решение ===
'''Заметим, что:'''
* Если первый элемент столбца больше <tex>x</tex>, то <tex>x</tex> находится в колонке слева.
* Если последний элемент строки меньше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной ниже.
Изначально рассматриваем матрицу <math>\alpha_k^m</math>.
==== Описание алгоритма ====
* Начнем с правого столбца и будем двигаться влево, рассматривая первые элементы этих столбцов.
* Если первый элемент столбца меньше искомого, то по правилу (1) мы можем выкинуть этот столбец.
* После того, как мы выкинули некоторые столбцы, получили новую матрицу. Будем рассматривать последние элементы ее строк.
* Если элемент меньше искомого, то нам нужно "двигаться вниз".
* Если не можем применить ни одно из правил, то поиск закончен. Осталось проверить элемент на равенство искомому.
Заметим, что мы можем применять эти правила, постепенно сокращая матрицу, пока в левом верхнем углу подматрицы не останется элемент, равный искомому.
====Рассмотрим решение на примере ====
[[Файл:Slice 1.png|280px|thumb|left|Состояние матрицы после первого шага]]
[[Файл:Slice2.png|280px|thumb|right|Состояние матрицы после второго шага]]
Будем искать элемент, значение которого - 46.
* Рассмотрим первые 3 строки. По правилу (2), искомый элемент находится ниже. Значит остаются только строки с 4 по 6.
* Рассмотрим последние 2 столбца. По правилу (1) искомый элемент находится левее. Значит остаются столбцы с 1 по 4.
* В левом верхнем углу матрицы остался элемент равный 46. Успех.
