假设我有一个已排序的矩阵 (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)) 的解决方案。有什么想法吗？？
对于这个任务，O(log (M * N)) 的解决方案不可行。
让我们来看一个简化版的任务：在“排序”的方阵中，假设所有次对角线（绿色）上面的元素都小于给定的数字，在次对角线下方（红色）的所有元素都大于给定的数字，并且没有其他假设关于次对角线（黄色）上的元素。
无论原始任务的假设还是这些额外的假设，都没有告诉我们次对角线上的元素如何相互关联。这意味着我们只有一个未排序的N个整数的数组。我们无法比O(N)更快地在未排序的数组中找到给定的数字。因此，对于正方形矩阵的原始（更复杂）问题，我们无法获得比O(N)更好的解决方案。
对于长方形矩阵，可以拉伸正方形图像并根据需要设置额外的假设。这里我们有min(N,M)个大小为max(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))))更好的解决方案。
1 2 3 4 5 6 … (n-2) (n-1) (n+1)
2 3 4 5 6 7 … (n-1) (n+1) (n+2)
3 4 5 6 7 8 … (n+1) (n+2) (n+3)
… … … … … … … … … …
(n-2) (n-1) … … … … … … … (2n-1)
(n-1) (n+1) … … … … … … … 2n
(n+1) (n+2) … … … … … (2n-1) 2n (2n+1)
如果你在这个矩阵中寻找n，你必须至少检查每一行一次，以确定n是否在该行中，因为n可能在任何一行中。(证明不完整，但是这里是思路)
您需要使用递归来解决这个问题。给定矩阵X和数字y，您可以在X的中间行上进行二分查找以将矩阵分成四个部分，使得：
A|B
---
C|D
所有A中的元素都小于y，所有D中的元素都大于y，y可以在B和C中。在B和C中迭代地查找y。
由于height(A)=height(B)≈height(C)=height(D)，size(X)>=2*(size(B)+size(C))，因此结果复杂度为O(logn)。
def find(X,y):
a,b = X.shape
i = a /2
j = binsearch(X[i,:], y)
if X[i,j]==y:
return True
else:
return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y )
由于行和列都是已排序的，如果我们查看每行的第一个元素，就可以找到包含我们要查找的数字的行。接着，我们可以利用每行中元素已排序的事实，找到该数字。
我知道的最快的搜索算法是二分查找，其复杂度为O(log n)，因此总复杂度将为O(log m + log n)。
以下是一个例子，假设我们要查找28：
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
O(MLog N)，对于每一行 (M) + 搜索 (log N)。 - noMAD我认为这可以在O(log(n*n)*log(n))的时间内完成，其中n是一个方阵的行数。
根据矩阵的性质，矩阵的主对角线是一个排序数组。因此，我们可以在O(log(n))的时间内搜索元素或其下限。现在，使用该元素作为枢轴，我们有4个子矩阵。我们可以说，子矩阵（左上）中的所有元素都较小，子矩阵（右下）中的所有元素都较大。因此，我们可以将其从搜索空间中删除。
现在，在子矩阵（右上）和子矩阵（左下）中进行递归搜索。
由于在每个步骤中，我们执行log(n)搜索（沿着主对角线），并且在每个步骤中最多可以减少一半的搜索空间，因此最多可能需要log(n*n)步。
因此，时间复杂度= O(log(n)log(nn))。
如果有任何错误，请纠正。
参考资料 - [书籍]Cracking the coding interview（问题11.6）
n = MxN，你怎么考虑将其视为一个数组进行搜索？ - noMAD