Поиск в матрице — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение за O(n\cdotlog(m)))
Строка 22: Строка 22:
 
Время работы может быть улучшено до <tex>O(min(n, m) \cdot log(max(n \cdot m))</tex>. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.
 
Время работы может быть улучшено до <tex>O(min(n, m) \cdot log(max(n \cdot m))</tex>. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.
  
 +
Существует еще один способ оптимизации. Рассмотрим случай, когда используется двоичный поиск по строке. Достаточно очевидно, что искомое число может находится только в тех строках, где первый элемент меньше искомого, а последний - больше. Перед началом поиска можно исключить 2 прямоугольных участка матрицы: первый состоит из строк, у которых последний элемент меньше искомого; второй состоит из строк, у которых первый элемент больше искомого. Используя двоичный поиск, можно найти границы этих участков за <tex>O(log(n))</tex> для столбцов и за <tex>O(log(m))</tex> строк.
  
 
== Решение за O(n + m) ==
 
== Решение за O(n + m) ==

Версия 15:28, 23 января 2016

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


Определение:
Отсортированная матрица - матрица, для которой выполнено следующее условие: [math] a[row][col] \le a[row + 1][col], a[row][col] \le a[row][col + 1] [/math]


Пример отсортированной матрицы

Решение за O(n[math]\cdot[/math]m)

Для начала рассмотрим наивный алгоритм поиска элемента. В каждой строке исходной матрицы запускаем линейный поиск, если находим элемент, то возвращаем его координаты [math](row, col)[/math]. Время работы — [math]O(n \cdot m)[/math].


Решение за O(n[math]\cdot[/math]log(m))

Данный способ решения использует наивное решение за [math]n \cdot m[/math], улучшенное с помощью двоичного поиска. Для этого в каждой строке запускается двоичный поиск. Время работы — [math]O(n \cdot log(m)[/math].

Замечание

Время работы может быть улучшено до [math]O(min(n, m) \cdot log(max(n \cdot m))[/math]. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.

Существует еще один способ оптимизации. Рассмотрим случай, когда используется двоичный поиск по строке. Достаточно очевидно, что искомое число может находится только в тех строках, где первый элемент меньше искомого, а последний - больше. Перед началом поиска можно исключить 2 прямоугольных участка матрицы: первый состоит из строк, у которых последний элемент меньше искомого; второй состоит из строк, у которых первый элемент больше искомого. Используя двоичный поиск, можно найти границы этих участков за [math]O(log(n))[/math] для столбцов и за [math]O(log(m))[/math] строк.

Решение за O(n + m)

В данном решении мы начинаем поиск из правого верхнего угла и движемся к искомому элементу. Идея алгоритма в том, что если текущий элемент меньше необходимого, то мы сдвигаемся на одну строку вниз. Если он больше, то мы сдвигаемся на одну колонку вправо.



Код

 if (target < a[0][0] || target > a[N-1][N-1]) 
   return false;
 row = 0;
 col = N-1;
   while (row <= N-1 && col >= 0) {
     if (a[row][col] < target) 
       row++;
     else if (a[row][col] > target)
       col--;
     else
       return true;
 return false;
Пример поиска числа 13 в матрице

Оценка времени работы

Очевидно, что во время работы указатель сдвигается максимум на n строк и m столбцов. В этом случае время работы составляет [math]O(n + m)[/math].