Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to efficiently search in an ordered matrix? [duplicate]

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 

How to search this matrix for a number in 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.

like image 459
Ashley Avatar asked Sep 16 '10 02:09

Ashley


People also ask

How do you find the elements in a sorted matrix?

Naive approach: The simple idea is to traverse the array and to search elements one by one. Algorithm: Run a nested loop, outer loop for row and inner loop for the column. Check every element with x and if the element is found then print “element found”

How do I find the row and column of a matrix in C++?

I know in C++ you can get a arrays amount of rows and columns with: int rows = sizeof array / sizeof array[0]; int cols = sizeof array[0] / sizeof array[0][0];


2 Answers

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.

  • 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.

  • 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).

Pseudo 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 
like image 145
codaddict Avatar answered Sep 21 '22 17:09

codaddict


Split the Matrix in 4 submatrices. If bottom right of a sub-matrix is less than key, discard it. If the top left of a sub-matrix is bigger than the key, discard it. Repeat the splitting procedure for the remaining sub-matrices.

[Update] For some pseudo code (and a discussion of complexity) see Jeffrey L Whitledge's answer of this question.

like image 36
Landei Avatar answered Sep 20 '22 17:09

Landei