如何在一个有序的矩阵有效地搜索？ [英] How to efficiently search in an ordered matrix?

问题描述

我有一个 X 按是矩阵，其中每行和每列按升序排列如下给出

I have a x by y matrix, where each row and each column are in ascending order as given below.

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

如何搜索这个矩阵的数量 O（X + Y）？

有人问我这个问题接受采访，但无法弄清楚的方式。想知道它是否可以做。

I was asked this question for an interview, but could not figure out the way. Curious to know if it could be done.

推荐答案

开始在第一行（右上角）的最后一个元素。
它与键比较。我们有三个情况：

Start at the last element of the first row(top-right corner).
Compare it with the key. We have 3 cases:

• 如果他们是平等的，我们都做了。

• If they are equal we are done.

如果键大于元素 那么就意味着键不可能是present 该行因此移动搜索 它下面的元素。

If key is greater than that element then it means key cannot be present in that row so move the search to the element below it.

如果键小于该元素则 这意味着键可能是present在 行向左且不能present在列进一步向下，所以移动搜索 到了左边的元素。

If key is less than that element then it means key could be present in that row towards left and cannot be present in the column further down, so move the search to the element left of it.

继续做下去，直到你找到的元素，或者你不能再动（项不存在）。

Keep doing it till you find the element or you cannot further move(key does not exist).

伪code：

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

这篇关于如何在一个有序的矩阵有效地搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！