假设我有一个矩阵（MxN），其中的行和列已排序。
MxN
例：
[1 5 8 20]
[2 9 19 21]
[12 15 25 30]
我必须查找矩阵中是否存在给定的数字（基本搜索）。我有一个运行的算法O(n)
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))解决方案。有任何想法吗？？
O(log (MxN)) == O(Log(n))
O（log（M * N））解决方案无法完成此任务。
让我们看一个简化的任务：在“排序的”方矩阵中，假设次要对角线（绿色）上方的所有元素均小于给定数，次要对角线（红色）下方的所有元素均大于给定数，并且次要对角线上的元素（黄色）。
该任务的原始假设或这些附加假设都没有告诉我们次要对角线上的元素如何相互关联。这意味着我们只有N个整数的未排序数组。我们无法在未排序的数组中找到给定的数字快于O（N）。因此，对于原始的（较复杂的）方矩阵问题，我们无法获得比O（N）更好的解决方案。
对于矩形矩阵，拉伸正方形图片并相应地设置其他假设。在这里，我们有大小分别为max（N，M）/ min（N，M）的min（N，M）个排序的子数组。最好的搜索方法是使用线性搜索来查找一个或几个可能包含给定值的子数组，然后在这些子数组中使用二进制搜索。在最坏的情况下，有必要在每个子阵列中进行二进制搜索。复杂度为O（min（N，M）（1+ log（max（N，M）/min（N，M）））））。所以对于矩形矩阵的原始问题（更复杂的问题），我们无法获得比O（min（N，M）（1 +log（max（N，M））-log（min（N，M）））更好的解决方案）。
