[9.6] Find an element in sorted matrix

1. Example


// RIGHT MOST => LARGER next row.

// => LESS left col
123
456
789

find 5, ROW should be 1
m = 0+2 /2 = 1, 4 < 5, l = 1+1 =2
m= 2+2  /2 =2, 7 > 5, r = 2-1 =1, l > r , STOP
1,4,7
4=> 4,5,6


find 3 , ROW should be 0
m=0+2 /2 =1 , 4 > 3 , r = m-1 = 0
m = 0+ 0  /2 = 0, 1 < 3 , l = 0+1 =1 , l >r, STOP

find 9, ROW should be 2
m=0+2 /2 = 1 , 4 < 9, l = m+1 = 2
m = 2+2 /2  =2 , 7 < 9, l = 2+1 =3, l > r=2 , STOP



2. Implementation

public boolean FindElem(int[][] matrix, int target, int M, int N)
{



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





      int l = 0;
      int r = M;
      //while ( l < r)
      while( l <= r)
      {
           int m = (l+r)/2;
           if (  martix[m][0] == target)
              return true;
           if ( matrix[m][0] < target )
                 l = m+1;
           else
                 r = m-1;
      }
      



      // NOTE: 
      //int row = l;
      if ( r < 0)
             return false;
      int row = r;




      int l = 0;
      int r = N;
      while ( l <= r)
      {
            int m = (l+r)/2;
           if ( matrix[row][m] == target)
                return true;
           if ( matrix[row][m] < target)
                l = m+1;
            else
                r = m-1;
      }


   
     
       return false;



} 

// RIGHT MOST => LARGER next row.
//            => LESS left col
public boolean FindElem(int[][] matrix, int target, int M, int N)
{


     int row = 0; 
     int col = N-1;

  


     while ( row < M && col >=0 )
     {
          if (  matrix[row][col] == target  )
               return true; 
          else if (   martix[row][col] > target ) //1,2,3=> 3 > 2
               col--;
          else // 1,4,7 
          {
               row++
          }
     }  



     return false;



}

3. Similar Ones