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

Question

我有一个x由y矩阵,其中每行和每列是按升序排列如下面给出的.

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

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

我被问到这个问题接受采访,但无法弄明白.很想知道它是否可以完成.

Answer 1

从第一行的最后一个元素开始(右上角).
比较它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

Answer 2

在4个子矩阵中拆分矩阵.如果子矩阵的右下角小于键,则丢弃它.如果子矩阵的左上角大于键,则丢弃它.对剩余的子矩阵重复拆分过程.

[更新]对于一些伪代码(以及对复杂性的讨论),请参阅Jeffrey L Whitledge 对此问题的回答.