title: Find number in sorted matrix (Rows n Columns) in O(log n)
body: <p>Say I have a matrix (<code>MxN</code>) which has its rows and columns sorted. </p>
  
  <ol>
  <li>All the elements in each row are arranged in increasing order</li>
  <li>All the elements in each column are arranged in increasing order</li>
  <li>All the elements are integers</li>
  <li><p>No other assumptions can be made</p>
  
  <p><strong>Example:</strong> </p>
  
  <p>[1  5  8  20]</p>
  
  <p>[2  9  19 21]</p>
  
  <p>[12 15 25 30]</p></li>
  </ol>
  
  <p>I have to find if a given number is present in the matrix or not (Basic search). I have an algorithm which runs <code>O(n)</code></p>
  
  <pre><code>int row = 0;
  int col = N-1;
  
  while (row &lt; M &amp;&amp; col &gt;= 0) {
    if (mat[row][col] == elem) { 
      return true;
    } else if (mat[row][col] &gt; elem) { 
      col--;
    } else { 
      row++;
    } 
  }
  </code></pre>
  
  <p>But I was asked an <code>O(log (MxN)) == O(Log(n))</code> solution. Any ideas??</p>