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