[Search][BinarySearch][Matrix] Search a 2D Matrix

1. Example
each row is sorted
the first integer of each row is greater than the last integer of previous row
[
[1,3,5,7],
[10,11,16,20],
[23,30,34,50]
]

Given target = 3, return true


2. Implementation
Complexity:O(log(m)+log(n)), Space:O(1)
Binary Search
First locate which row, BS to find the target is between two value and choose previous one's row
=> Search Insert Position, its goal is to find two indexes which are two bound for the target value

public boolean searchMatrix(int[][] matrix, int target)
{



     // validate the input
     if (matrix==null || matrix.length == 0 || matrix[0].length ==0)
     {
          return false;  
     }
     





     int l=0;
     int r= matrix.length-1;
     while(l<=r) 
     {
          int m = (1+r)>>1;
          if ( matrix[m][0] == target)
          {
              return true;
          }
          else if ( matrix[m][0] > target )
          {
              r = m-1;
          }
          else 
          {
              l = m+1;
          }
     }
 




     // NOTE: if target larger than first integer in the last row, l=m+1 out of bound, so we take r value
     // NOTE: if target less than second integer in the second row, 
l= m+1 point to second row, so we take r value
     if (  r < 0 )
     {
         return false;// target is less than the first integer of the first row
     }
     int row = r;
     int l = 0;
     int r = matrix[0].length -1;
     while (l<=r)
     {
         int m = (l+r)>>1;
         if ( matrix[row][m] == target)
         { 
             return true;
         }
         else if ( matrix[row][m] > target )
         {
             r = m-1;   
         }
         else 
         {
             l = m+1;
         }
     }




     return false;




}

3. Similar Ones
 Search for a Range
 Search Insert Position
 Search in Rotated Sorted Array I and II

 Set Matrix Zeroes
 Spiral Matrix I and II
 Rotate Image