Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Naive Way: There lies a linear approach O(n+m).

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     // edge case  
     if(matrix==null || matrix.length==0) return false;  
     // general case  
     int i = 0, j = matrix[0].length-1;  
     while(i < matrix.length && j >= 0){  
       if(matrix[i][j] == target) return true;  
       if(matrix[i][j] > target) j--;  
       else i++;  
     }  
     return false;  
   }  
 }  

The idea is to start from upper right. If current number is larger than target, that means you cannot find target in current row. So turn to next row. If current number is smaller than target, that means the target must lie in current row.

Improved Way: Could use a binary search approach to search current row/column. Speed up the approach to O(logn + logm) = O(log(nm))

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     // edge case  
     if(matrix==null || matrix.length==0) return false;  
     // general case  
     int row = binarySearch(matrix, target);  
     if(row==-1) return false;  
     int col = binarySearch(matrix[row], target);  
     return col!=-1;  
   }  
   private int binarySearch(int[][] matrix, int target){  
     int low = 0, high = matrix.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(matrix[middle][0] <= target && middle==matrix.length-1) return middle;  
       if(matrix[middle][0] <= target && matrix[middle+1][0] > target) return middle;  
       if(matrix[middle][0] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return low;  
   }  
   private int binarySearch(int[] array, int target){  
     int low = 0, high = array.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(array[middle] == target) return middle;  
       if(array[middle] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return -1;  
   }  
 }