我有一个任务，需要编写一个算法（不是任何特定语言，只是伪代码），接收一个以特定方式排序的矩阵[大小：M x N]，其中所有行都已排序并且所有列也各自排序，并在该矩阵中查找某个特定值。我需要编写最高效的算法。
该矩阵看起来像：
1 3 5
4 6 8
7 9 10
我的想法是从第一行和最后一列开始，简单地检查值。如果它更大，则向下移动；如果它更小，则向左移动，并继续这样做，直到找到该值或索引超出边界（如果该值不存在）。这个算法的时间复杂度为线性O(m+n)。我被告知可以使用对数复杂度来实现。是否可能？如果可能，如何实现？
a ..... b ..... c
. . . . .
. 1 . 2 .
. . . . .
d ..... e ..... f
. . . . .
. 3 . 4 .
. . . . .
g ..... h ..... i
并具有以下属性：
a,c,g < i
a,b,d < e
b,c,e < f
d,e,g < h
e,f,h < i
因此，矩阵右下角的值（例如i）始终是整个矩阵中最大的值，并且如果将矩阵分成4个相等的部分，则此属性是递归的。
因此，我们可以尝试使用二进制搜索：
因此，算法可能如下所示：
input: X - value to be searched
until found
divide matrix into 4 equal pieces
get e,f,h,i as shown on picture
if (e or f or h or i) equals X then
return found
if X < e then quarter := 1
if X < f then quarter := 2
if X < h then quarter := 3
if X < i then quarter := 4
if no quarter assigned then
return not_found
make smaller matrix from chosen quarter
对我来说，这似乎是一个O(log n)的算法，其中n是矩阵中元素的数量。它有点像二维的二分查找。我不能正式地证明它，但它类似于典型的二分查找。
for (int i = 0; i<M; i++)
for (int j=0; j<N; j++)
if (mat[i][j] == value) return tuple(i,j);
显然，我对这个问题的评论也应该放在这里: |
@sagar 但这不是教授给出的例子。否则他上面的方法是最快的（先检查行末，然后继续）。此外，首先检查中间行的末尾会更快，有点类似于二分搜索。
检查每一行的末尾（并从中间行的末尾开始）以找到内存数组中高于所检查数字的数字是最快的，然后在每个匹配的行上进行二分搜索，直到找到它。
在log M时间内，您可以获得能够包含目标的行范围（对行的第一个值进行二分查找，对行的最后一个值进行二分查找，仅保留那些第一个值小于等于目标且最后一个值大于等于目标的行）。两个二分查找仍然是O(log M)。
然后，在O(log N)时间内，您可以探索这些行中的每一行，同样使用二分查找！
这使得其为O(logM x logN)
tadaaaa
这是类似于Michal的回答（我将从中借鉴美丽的图形）的思路。
矩阵：
min ..... b ..... c
. . .
. II . I .
. . .
d .... mid .... f
. . .
. III . IV .
. . .
g ..... h ..... max
Min和Max分别是最小值和最大值。"mid"不一定是平均/中位数/任何值。
我们知道mid的值>=象限II中的所有值，并且<=象限IV中的所有值。我们不能对象限I和III做出这样的断言。如果我们递归，我们可以在每个级别消除一个象限。
因此，如果目标值小于mid，则必须搜索象限I、II和III。如果目标值大于mid，则必须搜索象限I、III和IV。
每步空间减少了3/4：
n * (3/4)x = 1
n = (4/3)x
x = log4/3(n)
对数只相差一个常数因子，因此这是O(log(n))。
find(min, max, target)
if min is max
if target == min
return min
else
return not found
else if target < min or target > max
return not found
else
set mid to average of min and max
if target == mid
return mid
else
find(b, f, target), return if found
find(d, h, target), return if found
if target < mid
return find(min, mid, target)
else
return find(mid, max, target)
//start from the top right corner
//if value = el, element is found
//if value < el, move to the next row, element can't be in that row since row is sorted
//if value > el, move to the previous column, element can't be in that column since column is sorted
function find(matrix, el) {
//some error checking
if (!matrix[0] || !matrix[0].length){
return false;
}
if (!el || isNaN(el)){
return false;
}
var row = 0; //first row
var col = matrix[0].length - 1; //last column
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === el) { //element is found
return true;
} else if (matrix[row][col] < el) {
row++; //move to the next row
} else {
col--; //move to the previous column
}
}
return false;
}
public static boolean find(int a[][],int rows,int cols,int x){
int m=0;
int n=cols-1;
while(m<rows&&n>=0){
if(a[m][n]==x)
return1;
else if(a[m][n]>x)
n--;
else m++;
}
}
这是错误的答案
我真的不确定任何一个答案是否是最优答案。我正在尝试。
我认为时间复杂度是2 *（log m + log n）。
如果输入数组是正方形（n * n），则可以通过沿对角线进行二分搜索来减少常数。
1 2 3 10，你被要求查找7。你会说它在第3行第3列，但事实并非如此。7可能在(2, 2)，而其余所有单元格都可以是999... - ihadanny关于获取对角线，然后在对角线上进行二分查找，从右下角开始检查是否在对角线上方，如果是，则将对角线数组位置作为所在列的列号，否则检查是否在下方。每次在列上运行二分查找一旦在对角线上有命中（使用对角线的数组位置作为列索引）。我认为这就是@user942640所说的。
您可以获得上述运行时间，并在需要时（某个时刻）将算法交换为在初始对角线数组上进行二分查找（考虑到其n * n元素并且获取x或y长度为O(1)，因为x.length = y.length。即使在百万*百万的二分查找中，如果对角线小于半步，则向上回退对角线，如果不小于，则向回二分查找到您所在的位置（这是在沿对角线进行二分查找时稍微更改的算法）。我认为对角线比沿行进行二分查找更好，只是我现在太累了，无法看数学 :)
顺便说一句，我认为运行时间与分析略有不同，你可以用最好/最坏/平均情况、时间与内存大小等方面来描述。因此，问题最好陈述为“在最坏情况分析中最好的运行时间是什么”，因为在最好情况下，你可以进行一次暴力线性扫描，并且该项可能位于第一个位置，这将比二分搜索更好的“运行时间”...这里是 n 的下限。从长度为 n 的未排序数组 A 开始。根据以下规则构建新矩阵 M：次对角线包含数组 A，其上方的元素均为负无穷，其下方的元素均为正无穷。行和列都已排序，在 M 中查找条目与在 A 中查找条目相同。