Search in a row wise and column wise sorted matrix

You are given an 2D array of MxN which is row and column wise sorted. What is the efficient way to search for an element?

Steps:
1) Start from top right element
2) for loop compare this element e with x
a) if they are equal then return its position
b) e < x then go down c) e > x then go to left
3) return false if limits go out of bound.

Implementation:

int search(int mat[4][4], int M, int N, int elem)
{
	int row = 0;
	int col = N-1;

	while (row < M && col >= 0)
	{
	  if (mat[row][col] == elem)
	  {
		return 1;
	  }
	  else if (mat[row][col] > elem)
	  {
		col--;
	  }
	  else
	  {
		row++;
	  }
	}
	return 0;
}

Time Complexity: O(n)

One Thought on “Search in a row wise and column wise sorted matrix

  1. You could also use a binary search using a pointer that fakes a one dimensional array using the subscripts, like this:

    // int *ptr = mat[ 0 ];.
    because..
    mat[ row ][ col ] = ptr[ row * columnSize + col ].

Leave a Reply to Pedro Henrique Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation