Make delicious recipes!

Search an element in a 2D array (matrix) sorted row-wise and col-wise

Linear search is O(N2) for an N by N matrix but doing that would mean that we are not using the sorted property of the matrix. We cannot apply binary search considering the matrix to be one array of length NxN because sorting is only per row and per column i.e. the matrix could have the following form:

   01   06    09
  
   03   08    12
  
   05   10    14

So we need to apply binary search in a different way.

Start from matrix[0][N] and use the following algorithm:

int i=0;
int j=N-1;

while (i < N && j >= 0)
{
  if (matrix[i][j] == searchEle)
    return true;
  if (matrix[i][j] < searchEle)
    i++;
  else 
    j--;
}
return false;

This solution is guaranteed to work because at every step we are eliminating a full row or columns which is less than or greater than the given element.

Search terminates when we reach the matrix limits i.e. 0 or N

Order of search: O(N)






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal