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

Linear search is O(N²) 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)