Найти число в отсортированной матрице (строк n столбцов) за O(log n) [дубликат]

На этот вопрос уже есть ответы здесь:

Как искать число в двумерном массиве, отсортированном слева направо и сверху вниз?(19 ответов)

Закрыт в прошлом году.

Скажем, у меня есть матрица ( MxN), строки и столбцы которой отсортированы.

Все элементы в каждой строке расположены в порядке возрастания
Все элементы в каждом столбце расположены в порядке возрастания
Все элементы являются целыми числами
Никакие другие предположения не могут быть сделаны

Пример:

[1 5 8 20]

[2 9 19 21]

[12 15 25 30]

Я должен найти, присутствует ли заданное число в матрице или нет (Базовый поиск). У меня есть алгоритм, который работает O(n)

int row = 0;
int col = N-1;

while (row < M && col >= 0) {
  if (mat[row][col] == elem) { 
    return true;
  } else if (mat[row][col] > elem) { 
    col--;
  } else { 
    row++;
  } 
}

. Но мне задали O(log (MxN)) == O(Log(n))решение. Есть идеи??

algorithm performance

задан noMAD 10 December 2013 в 19:37

0 ответов

Другие вопросы по тегам:

algorithm performance

Найти число в отсортированной матрице (строк n столбцов) за O(log n) [дубликат]

0 ответов

Похожие вопросы: