搜索排序矩阵的最有效方法？

Question

我有一个任务是编写一个算法（不是用任何特定的语言，只是伪代码），该算法接收一个矩阵 [大小：M x N]，该矩阵的排序方式是所有行都已排序并且所有列都已排序单独排序，并在该矩阵中找到某个值。我需要编写我能想到的最省时的算法。

矩阵看起来像这样：

1  3  5
4  6  8
7  9 10

我的想法是从第一行和最后一列开始，简单地检查该值，如果它更大，则向下移动，如果它小于，则向左移动，并继续这样做，直到找到该值或直到找到索引超出范围（如果该值不存在）。该算法的线性复杂度为 O(m+n)。有人告诉我可以用对数复杂度来做到这一点。是否可以？如果是这样，怎么办？

Answer 1

你的矩阵看起来像这样：

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 个相等的部分，则此属性是递归的。

所以我们可以尝试使用二分搜索：

1. 探测值，
2. 分成几部分，
3. 选择正确的部分（以某种方式），
4. 用新的部分转到 1。

因此，算法可能如下所示：

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 是矩阵中的元素数量。这是一种二分搜索，但是是二维的。我无法正式证明它，但类似于典型的二分搜索。

Answer 2

这就是示例输入的样子？按对角线排序？当然，这是一种有趣的类型。

由于下一行的值可能低于该行上的任何值，因此您不能对给定的数据行做出任何特定的假设。

我会（如果要求在大输入上执行此操作）将矩阵读入列表结构，该列表结构将数据作为一对元组，并将 mxn 坐标作为元组的一部分，然后对矩阵进行一次快速排序，然后根据值找到它。

或者，如果每个单独位置的值是唯一的，则将 MxN 数据放入以该值为键的字典中，然后根据输入的键（或输入的键的哈希值）跳转到 MxN 的字典条目）。

编辑：

请注意，如果您要多次查看矩阵，我上面给出的答案是有效的。如果您只需要解析一次，那么这就是您能做到的最快速度：

for (int i = 0; i<M; i++)
 for (int j=0; j<N; j++)
  if (mat[i][j] == value) return tuple(i,j);

---

显然我对这个问题的评论也应该放在这里：|

@sagar 但这不是教授给出的例子。否则他有上面最快的方法（首先检查行的末尾，然后继续）另外，首先检查中间行的末尾会更快，有点像二分查找。

检查每行的末尾（并从中间行的末尾开始）以查找高于内存数组中检查的数字的数字将是最快的，然后对每个匹配行进行二进制搜索，直到找到它。

Answer 3

在 log M 中，您可以获得能够包含目标的一系列行（对行的第一个值进行二分搜索，对行的最后一个值进行二分搜索，仅保留第一个 <= 目标和最后一个 >= 目标的行）两次二分查找仍然是 O(log M)
然后在 O(log N) 中，您可以再次使用二分搜索来探索每一行！

这使得它的复杂度为 O(logM x logN)
塔达阿阿

Answer 4

这符合 Michal 的回答（我将从中窃取漂亮的图片）。

矩阵：

  min ..... b ..... c
    .       .       .
    .  II   .   I   . 
    .       .       .
    d .... mid .... f
    .       .       .
    .  III  .   IV  .
    .       .       .
    g ..... h ..... max

Min 和 max 分别是最小值和最大值。 “mid”不一定是平均值/中位数/任何值。

我们知道中间的值>=象限II中的所有值，并且<=象限IV中的所有值。我们不能对第一象限和第三象限做出这样的主张。如果我们递归，我们可以在每一级消除一个象限。

因此，如果目标值小于中值，我们必须搜索象限 I、II 和 III。如果目标值大于mid，我们必须搜索象限I、III、IV。

每一步空间减少到之前的 3/4：

n * (3/4)^x = 1

n = (4/3)^x

x = log_4/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)

Answer 5

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++;
}

}

Answer 6

取出对角线，然后对对角线进行二分搜索，从右下角开始检查它是​​否在上面，如果是，则将对角线数组位置作为它所在的列，如果不是，则检查它是否在下面。每次在对角线上命中后对列运行二分搜索（使用对角线的数组位置作为列索引）。我认为这就是 @user942640 所说的，

你可以获得上面的运行时间，并且在需要时（在某些时候）交换算法以在初始对角数组上进行二分搜索（这是考虑到它的 n * n元素并获得 x 或 y 长度为 O(1)，因为 x.length = y.length 即使在百万 * 百万对角线中搜索，如果它小于对角线的半步，如果它不小于二进制。向后搜索你所在的位置（这是沿对角线进行二分搜索时对算法的轻微更改），我认为对角线比沿行进行二分搜索更好，我现在只是厌倦了查看数学:)

顺便说一句，我相信运行时间与分析略有不同，您会根据最佳/最差/平均情况以及时间与内存大小等来描述分析，因此问题最好表述为“什么是最好的”最坏情况分析中的运行时间”，因为在最好的情况下，您可以进行强力线性扫描，并且该项目可能位于第一个位置，这将是比二分搜索更好的“运行时间”...

Answer 7

这是n 的下限。从长度为 n 的未排序数组 A 开始。根据以下规则构造一个新矩阵 M：次对角线包含数组 A，其上方的所有内容均为负无穷大，其下方的所有内容均为正无穷大。行和列已排序，在 M 中查找条目与在 A 中查找条目相同。

Answer 8

JavaScript 解决方案：

//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;

}

Answer 9

这是错误的答案

我真的不确定是否有任何答案是最佳答案。我正在努力。

1. 二分查找第一行第一列，找出“x”可能所在的行和列。你会得到 0,j 和 i,0。如果在此步骤中未找到 x，则 x 将位于 i 行或 j 列。
2. 对步骤 1 中找到的第 i 行和第 j 列进行二分查找。

我认为时间复杂度是 2* (log m + log n)。

如果输入数组是正方形 (n * n)，则可以通过沿对角线进行二分搜索来减少常量。