Search in a row wise and column wise sorted matrix

Source


Problem
Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity.

Solution

int search(int mat[4][4], int n, int x)

{

int i = 0, j = n-1; //set indexes for top right element

while ( i <>= 0 )

{

if ( mat[i][j] == x )

{

printf("\n Found at %d, %d", i, j);

return 1;

}

if ( mat[i][j] > x )

j--;

else // if mat[i][j] <>

i++;

}

printf("\n Element not found");

return 0; // if ( i==n || j== -1 )

}




My solution

Consider an element in the main diagonal.

If you were to think about a matrix with current diagonal element as the last element (last row, last column) that element is bound to be the largest element in the sub matrix. So if the number which we are looking for is

greater then the current diagonal element, we move to next element in

the diagonal (downward).

Moment we find the number we are searching for to be less then the diagonal element.

We can apply binary search in the part of the column above the diagonal element or part of the row on the LHS of the diagonal element.

Complexity: worst case we have to traverse to the bottom most element in the diagonal:

N iteration + 2 * logn for (binary search in row and column)

O(n + 2*logn) => O(n)