相关疑难解决方法(0)

假设我有一个矩阵(MxN),其行和列已排序.

1. 每行中的所有元素按递增顺序排列
2. 每列中的所有元素按递增顺序排列
3. 所有元素都是整数

4. 没有其他假设可以做

   例:

   [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))解决方案.有任何想法吗？？