Esta questão já tem uma resposta aqui:

Como pesquiso um número em uma matriz 2D classificada da esquerda para a direita e de cima para baixo? 19 respostas

Diga eu tenho uma matriz (MxN) que tem suas linhas e colunas classificadas.

Todos os elementos em cada linha são organizados em ordem crescenteTodos os elementos em cada coluna são organizados em ordem crescenteTodos os elementos são inteiros

Nenhuma outra suposição pode ser feita

Exemplo:

[1 5 8 20]

[2 9 19 21]

[12 15 25 30]

Eu tenho que encontrar se um determinado número está presente na matriz ou não (pesquisa básica). Eu tenho um algoritmo que executaO(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++;
  } 
}

Mas me pediram umaO(log (MxN)) == O(Log(n)) solução. Alguma ideia??