title: How do I search for a number in a 2d array sorted left to right and top to bottom?
body: <p>I was recently given this interview question and I'm curious what a good solution to it would be.</p>
  
  <blockquote>
    <p>Say I'm given a 2d array where all the
    numbers in the array are in increasing
    order from left to right and top to
    bottom.</p>
    
    <p>What is the best way to search and
    determine if a target number is in the
    array?</p>
  </blockquote>
  
  <p>Now, my first inclination is to utilize a binary search since my data is sorted.  I can determine if a number is in a single row in O(log N) time.  However, it is the 2 directions that throw me off.</p>
  
  <p>Another solution I thought may work is to start somewhere in the middle.  If the middle value is less than my target, then I can be sure it is in the left square portion of the matrix from the middle.  I then move diagonally and check again, reducing the size of the square that the target could potentially be in until I have honed in on the target number.</p>
  
  <p>Does anyone have any good ideas on solving this problem?</p>
  
  <p>Example array:  </p>
  
  <p>Sorted left to right, top to bottom.</p>
  
  <pre><code>1  2  4  5  6  
  2  3  5  7  8  
  4  6  8  9  10  
  5  8  9  10 11  
  </code></pre>