title: Searching a 2D Array at sublinear time
body: <p>This is a problem from a recent coding interview</p>
  
  <p>Write an efficient algorithm that searches for a value in an m x n matrix. </p>
  
  <p>This matrix has the following properties:</p>
  
  <ol>
  <li><p>Integers in each row are sorted in ascending from left to right.</p></li>
  <li><p>Integers in each column are sorted in ascending from top to bottom.<br>
  .</p>
  
  <pre><code>  [1,   4,  7, 11, 15]
  
    [2,   5,  8, 12, 19]
  
    [3,   6,  9, 16, 22]
  
    [10, 13, 14, 17, 24]
  
    [18, 21, 23, 26, 30]
  </code></pre></li>
  </ol>
  
  <p>Is there a way to do this below O(mn). I can't see how one can do a binary search on this array, since there's no way to eliminate anything.</p>