Search in sorted matrix

Search element in a sorted matrix

Today’s problem search in sorted matrix, that is to find an element in column and row sorted matrix. For example, given matrix is as below and element to be searched is 11, then output should be (2,2).

1,5,9, 13 
2,6,10,14
3,7,11,15
4,8,12,16

This problem is frequently asked to check understanding of binary search algorithm.

Search in sorted matrix : Algorithm

Brute force solution would be to scan all mXn elements and find the element. This approach has complexity of O(n2). Can we optimize it?
As mentioned in problem statement, each row and column is sorted.How can we use this information? Based on value of key and current element, we can discard some part of matrix.
Start from left-bottom most element of matrix. We know that it is greatest in first column and least in last row.
Check if element is key, if yes return index (i,j)
If it is not equal to key, then check if it is less than key, then move column to right as all above element in this column will be less than current column element and hence Key can not be in this column.
If current element is greater than key, check in row above current row as all elements on below of current element are greater and key can not be there.
Repeat these steps till we either find the key or we have examined all possible candidates.

Search in sorted matrix : implementation

#include <stdio.h>
 
int search_matrix(int a[4][4], int N, int M, int key){
 
    int i, j;
    int element;
    i = M-1;
    j = 0;
    while(i>=0 && j<N){ element = a[i][j]; 
    if(element == key) { 
         printf("Element found at (%d, %d)", i, j); return 0;
    } 
    if(element > key){
        /* If current element is greater than Key,
            we move up in matrix */
            i--;
        }
        else
        /* If current element is less than key,
           we move right of the matrix */
           j++;
    }
 	printf("Nothing found!!");
    return -1;
}
 
int main(void) {
	int a[4][4] = {
		       1,2,3,4,
		       5,6,7,8,
		       9,10,11,12,
		       13,14,15,16
	};
	
   	search_matrix( a, 5,5, 11);
	return 0;
}

Let’s see how it works. We will use the same matrix as in code and we are searching for 11.
We start from left bottom most cell. Element at that cell is 13, which is greater than key. In this case, we should be moving up the column, means decrease the row.
search in sorted matrix

Now, the element to be considered is 9 which is less than key, hence we move in same row to right.
binary search problems

Next is element 10, which is less than key, hence we again move right.
binary search questions

Now when move right, we hit element equals to key and we return the indices.

Complexity of binary search algorithm to find an element in sorted matrix is O(M+N) where M and N are rows and column of the matrix respectively.

Please share if there is something wrong or missing. If you are interested to contribute and earn money, please contact us.