Matrix Sorted Search Problem

Given a Matrix of size n*n and an element E to search in the Matrix. Each row and each column of the Matrix is sorted. We need to find an efficient algorithm to search this matrix.

Solution:

Take the last element of the first row and go either down or left using the following logic:

1. If the search element E is greater than the current element go down one step. i.e change the row to the next row.

2. If the search element E is less than the current element then go one step to the left. i.e change the col = col - 1.

Do the above operation till u find the element E or you have reached the end of the Matrix. End of the Matrix means we cannot move either to left or down.

Runtime of the algorithm would be around O(n).