Searching for an element in the sorted matrix

Example of the array can be

int[][] matrix = {
                   {1,3,5,7,9},
                   {10,12,14,16,18},
                   {19,21,23,25,27},
                   {28,30,32,34,36},
                   {37,39,41,43,45}
                };

This can be done using the following algorithm. 

We start our search with the top right element. 

• If it is equal to the key, we print corresponding indices and we are done!. 
• If the key is greater than the current element, we move to the next row because all the elements in the current row prior to this element are lesser. 
• If the key is less than the given element, we move to the previous column.  The reason is similar to the above.

We continue this search until we find the key or until we confirm the element is not present. If we reach last row first column, we can confirm that the element is not present.

Here is the java implementation of the above algorithm. The time complexity of this program is O(n) and n is the number of rows and columns.