如何在有序矩阵中高效搜索？

Question

我有一个 x by y 矩阵，其中每行和每列均按升序排列，如下所示。

1   5   7    9
4   6   10   15
8   11  12   19
14  16  18   21

如何在这个矩阵中搜索 O(x+y) 中的数字？

我面试时被问到这个问题，但不知道怎么回答。很想知道是否可以做到。

Answer 1

从第一行的最后一个元素（右上角）开始。
将其与键进行比较。我们有 3 种情况：

• 如果它们相等，我们就完成了。

• 如果key大于该元素
  那么这意味着 key 不能存在
  在该行中移动搜索
  到其下面的元素。

• 如果 key 小于该元素，则
  这意味着 key 可能存在于其中
  向左行并且不能出现在更下方的列中，因此将搜索移动
  到它左边的元素。

继续这样做，直到找到该元素，否则您无法进一步移动（键不存在）。

伪代码：

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = C-1

found = false
while( i>=0 && i<R) && (j>=0 && j<C) )
   if (matrix[i][j] == key )
      found = true
      break
   else if( matrix[i][j] > key )
       j--
   else if( matrix[i][j] < key )
       i++
end-while

Answer 2

将矩阵拆分为 4 个子矩阵。如果子矩阵的右下角小于 key，则丢弃它。如果子矩阵的左上角大于键，则丢弃它。对剩余的子矩阵重复分裂过程。

[更新]
对于一些伪代码（以及复杂性的讨论），请参阅 Jeffrey L Whitledge 的回答 这个问题。

Answer 3

// the matrix is like this, from left to right is ascending, and
// from down to up is ascending, but the second row'start is not always bigger than the first row's end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/
// 1   5   7    9
// 4   6   10   15
// 8   11  12   19
// 14  16  18   21
// time complexity is O(x+y), x is the count of row, and y is the count of column

public boolean searchMatrix2(int[][] matrix, int target) {
    int rowCount = matrix.length;
    if(rowCount == 0) return false;

    int colCount = matrix[0].length;
    if(colCount == 0) return false;

    //first find the target row, needs O(x)
    int targetRow = 0;
    while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) {
        targetRow++;
    }
    //than find the target in the target row, needs O(y), so the total is O(x)+O(y)
    boolean result = false;
    for(int i = 0; i < colCount; i ++) {
        if(matrix[targetRow][i] == target) {
            result = true;
            break;
        }
    }
    return result;
}

实际上，我们可以使用两次二分查找，先通过二分查找找到目标行，然后通过二分查找找到该行中的目标，所以时间复杂度为 O(lgx) + O(lgy)，即 O(lgx + lgy) )，O(x+y) 更好。