说我有一个矩阵（的M×N ），它有它的行和列进行排序。

Say I have a matrix (MxN) which has its rows and columns sorted.

没有其他假设可 All the elements in each row are arranged in increasing order All the elements in each column are arranged in increasing order All the elements are integers

No other assumptions can be made

示例：

[1 5 8 20]

[1 5 8 20]

[2 9 19 21]

[2 9 19 21]

[12 15 25 30]

[12 15 25 30]

我要找到一个给定的数字是present在基质或没有（基本搜索）。我有它运行 O（N）

I have to find if a given number is present in the matrix or not (Basic search). I have an algorithm which runs 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（日志（MXN））== O（日志（N））解决方案。任何想法??

But I was asked an O(log (MxN)) == O(Log(n)) solution. Any ideas??

推荐答案

O（日志（M * N））解决方案是不可能完成这个任务。

O(log (M * N)) solution is not possible for this task.

让我们来看一个简单的任务：在排序方阵承担上述二次角（绿色）的所有元素小于给定的数字，低于二级对角线（红色）大于给定的数字为元素的所有元素，并没有额外的假设上二次对角线（黄色）。

Let's look at a simplified task: in "sorted" square matrix assume all elements above secondary diagonal (green) less than given number, all elements below secondary diagonal (red) greater than given number, and no additional assumptions for elements on secondary diagonal (yellow).

无论此任务的原始假设，也不这些额外的假设告诉我们的次级对角线元素是如何彼此相关。这意味着我们只是有N个整数排序的数组。我们无法找到给出的无序数组中的一些快于O（N）。因此，对于原来的（更复杂）的问题方阵，我们无法得到一个解决方案，为O（N）更好。

Neither original assumptions of this task, nor these additional assumptions tell us how elements on secondary diagonal are related to each other. Which means we just have an unsorted array of N integers. We cannot find given number in the unsorted array faster than O(N). So for original (more complicated) problem with square matrix we cannot get a solution better than O(N).

有关的长方形矩阵，舒展的正方形图片，并设置相应的额外的假设。这里，我们有分钟（N，M）排序尺寸最大的子阵列（N，M）/分钟（N，M）的每个。这里搜索最佳的方法是使用线性搜索找到的一个或几个子阵列可含有给定值，然后使用这些子阵列内的二进制搜索。在最坏的情况下，有必要对每个子阵列中的二进制搜索。复杂度为O（分（N，M）*（1 +日志（MAX（N，M）/分钟（N，M））））。因此，对于原来的（更复杂的）问题的方形矩阵，我们不能得到一个解决方案，为O（分（N，M）*（1 +日志（MAX（N，M））好 - 日志（分（N，M））） ）。

For a rectangular matrix, stretch the square picture and set the additional assumptions accordingly. Here we have min(N,M) sorted sub-arrays of size max(N,M)/min(N,M) each. The best way to search here is to use linear search to find one or several sub-arrays that may contain given value, then to use binary search inside these sub-arrays. In the worst case it is necessary to binary-search in each sub-array. Complexity is O(min(N,M) * (1 + log(max(N,M) / min(N,M)))). So for original (more complicated) problem with rectangular matrix we cannot get a solution better than O(min(N,M) * ( 1 + log(max(N,M)) - log(min(N,M)))).