如何有效地搜索有序矩阵？

问题内容：

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

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

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

有人问我这个问题进行面试，但找不到答案。好奇地知道是否可以做到。

问题答案：

从第一行的最后一个元素（右上角）开始。
与进行比较key。我们有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

如何有效地搜索有序矩阵？

微信关注