title: find an element in a sorted matrix
body: <p>Problem:
  Given a matrix in which each row and each column is sorted, write a method to find an element in it. </p>
  
  <p>It is a classic interview question, here is my solution</p>
  
  <pre><code>boolean F(int[][] matrix, int hs, int he, int ws, int we)
  {
      if (hs &gt; he || ws &gt; we) 
          return false; 
  
      int m = (hs + he) / 2; 
      int n = (ws + we) / 2;
  
      if (matrix[m][n] == t)
      {
          return true;
      }
      else if (matrix[m][n] &lt; t)
      {
          // find the ele in the same row, right to [m][n]
          F(m, m, n + 1, we);
  
          // find the ele in the same col, upper to [m][n]
          F(m + 1, he, n, n);
  
          // find the ele in the area, where i&gt;m,j&gt;n 
          F(m + 1, he, n + 1, we);       
      } 
      else if (matrix[m][n] &gt; t)
      {
          // very similar to previous part
      }
  }
  </code></pre>
  
  <p>The running time of the algorithm is log(m) + log(n). I am looking for an algorithm that is more efficient, or with concise code.</p>
  
  <p>Having more comments, I come up with following code:</p>
  
  <pre><code>// return target recurrence in the matrix
  int F(int[][] m, int rs, int re, int cs, int ce, int t){
     int r1 = rs, r2 = re;
     int c1 = cs, c2 = ce;
     int r=0 , c = c1;
  
     while( r1 &lt; r2 &amp;&amp; c1 &lt; c2 ){
     // find the last element that &lt;= t in column c
       r  = FlastLess( r1, r2, c, t)
  
       if( r == -1 ) break;
  
       else{
         // find the first ele in the row that is &gt;=t
         c = FfirstGreater( r, c1, c2, t);
  
         if( c == -1)  break;
         else{
           r2 = r; 
           c1 = c; 
         }// else    
       }// else 
     }// while
  }// f
  </code></pre>
  
  <p>Here is the link to function F1 and F2 
  <a href="https://stackoverflow.com/questions/6553970/find-the-first-element-in-an-array-that-is-greater-than-the-target">Find the first element in a sorted array that is greater than the target</a></p>
  
  <pre><code>void FlastLess(int s, int e, int t){
    int l = s, h = e;
    while( l != h ){
       int mid = (l+h)/2;
       if( mid &gt;=  t) high = mid - 1; 
       else {
         if( high &lt; t) low= mid + 1;
         else low = mid;
       } 
    }
  
   void FfirstGreater(int s, int e, int t){
    while(l &lt; h){
      mid = (l+h)/2;
      if ( mid &lt;=  t) low = mid+1;
      else high = mid;
    }
   }
  
  }
  </code></pre>