Find an element in 2D sorted array or search target element in 2D sorted array

Problem : We have to find key element in the sorted 2D array - which is sorted row and column wise.

Brute force approach :  Iterate 2D array and find whether that element is present or not. It's obvious but not a satisfactory solution. Complexity will be  O(n^2) .So we can think of  something in order of O(logn) or O(n).
we can have several method using binary search or via zig-zag movement of matrix.
One of best possible solution :  (using Zig-zag movement)
logic behind this is that we will start from top right corner of matrix and will reach to bottom left , so we have three possible option to move on either left , bottom or diagonally. But given matrix is sorted in row and column wise ,so we will drop the idea of moving diagonally here.
Now we can move either in left or bottom which will be decided by comparing key and matrix elements.
Pseudo explanation :

 if ( key == matrix(row,column) )  
     key is found here @ (row,column)  
 else if(key > matrix(row, column))  
      Move in column wise , since element which i am looking for must be below the  
      current elements (since elements are sorted.)  
 else  
     Move in left direction  

Picture speaks better that text

Now we can write sample code in java as follows :

 public class FindAnElementin2DSortedArray {  
   public FindAnElementin2DSortedArray() {  
     super();  
   }  
   //zig zag matehod with O(n) complexity  
   public static boolean findByZigzagMethod(int[][] mat, int m, int n, int key) {  
     int row = 0, col = n - 1;  
     while (row < m && col >= 0) {  
       if (mat[row][col] == key) {  
         return true; // key==matrix(row, column) so return true.
       }  
       if (mat[row][col] < key)  
         row++;  
       else  
         col--;  
     }  
     return false; //control reach here means key not found.
   }  
   public static void main(String[] args) {  
     FindAnElementin2DSortedArray findAnElementin2DSortedArray = new FindAnElementin2DSortedArray();  
     int[][] mat = {{2,3,4},{8,12,13},{10,15,18}};  
     System.out.println(FindAnElementin2DSortedArray.findByZigzagMethod(mat, 3, 3,10));   
   }  
 }  

Sample output : true

When we run this program we find that key is found there and it returns true.


Reference: http://leetcode.com/2010/10/searching-2d-sorted-matrix.html