Поиск элемента в матрице
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
| Задача: |
| Дана матрица . Все столбцы и строки матрицы отсортированы. Требуется найти заданный элемент . |
Содержание
Варианты решения
Наивное решение
Заметим, что:
- Если первый элемент столбца больше , то находится в колонке слева.
- Если последний элемент строки меньше , то находится в строке, расположенной ниже.
Изначально рассматриваем матрицу .
Описание алгоритма
- Начнем с правого столбца и будем двигаться влево, рассматривая первые элементы этих столбцов.
- Если первый элемент столбца меньше искомого, то по правилу (1) мы можем выкинуть этот столбец.
- После того, как мы выкинули некоторые столбцы, получили новую матрицу. Будем рассматривать последние элементы ее строк.
- Если элемент меньше искомого, то нам нужно "двигаться вниз".
- Если не можем применить ни одно из правил, то поиск закончен. Осталось проверить элемент на равенство искомому.
Заметим, что мы можем применять эти правила, постепенно сокращая матрицу, пока в левом верхнем углу подматрицы не останется элемент, равный искомому.
Рассмотрим решение на примере
Будем искать элемент, значение которого - 46.
- Рассмотрим первые 3 строки. По правилу (2), искомый элемент находится ниже. Значит остаются только строки с 4 по 6.
- Рассмотрим последние 2 столбца. По правилу (1) искомый элемент находится левее. Значит остаются столбцы с 1 по 4.
- В левом верхнем углу матрицы остался элемент равный 46. Успех.
