Поиск элемента в матрице

Материал из Викиконспекты
Перейти к: навигация, поиск
Задача:
Дана матрица [math]\alpha_k^m[/math]. Все столбцы и строки матрицы отсортированы. Требуется найти заданный элемент [math]x[/math].


Варианты решения

Наивное решение

Заметим, что:

  • Если первый элемент столбца больше [math]x[/math], то [math]x[/math] находится в колонке слева.
  • Если последний элемент строки меньше [math]x[/math], то [math]x[/math] находится в строке, расположенной ниже.

Изначально рассматриваем матрицу [math]\alpha_k^m[/math].

Описание алгоритма

  • Начнем с правого столбца и будем двигаться влево, рассматривая первые элементы этих столбцов.
  • Если первый элемент столбца меньше искомого, то по правилу (1) мы можем выкинуть этот столбец.
  • После того, как мы выкинули некоторые столбцы, получили новую матрицу. Будем рассматривать последние элементы ее строк.
  • Если элемент меньше искомого, то нам нужно "двигаться вниз".
  • Если не можем применить ни одно из правил, то поиск закончен. Осталось проверить элемент на равенство искомому.

Заметим, что мы можем применять эти правила, постепенно сокращая матрицу, пока в левом верхнем углу подматрицы не останется элемент, равный искомому.

Рассмотрим решение на примере

Состояние матрицы после первого шага
Состояние матрицы после второго шага

Будем искать элемент, значение которого - 46.

  • Рассмотрим первые 3 строки. По правилу (2), искомый элемент находится ниже. Значит остаются только строки с 4 по 6.
  • Рассмотрим последние 2 столбца. По правилу (1) искомый элемент находится левее. Значит остаются столбцы с 1 по 4.
  • В левом верхнем углу матрицы остался элемент равный 46. Успех.