title: Two dimensional array search in sub linear time
body: <p>Today I was asked the following question in an interview:</p>
  
  <p>Given an n by n array of integers that contains no duplicates and values that increase from left to right as well as top to bottom, provide an algorithm that checks whether a given value is in the array.</p>
  
  <p>The answer I provided was similar to the answer in this thread: <br>
  <a href="https://stackoverflow.com/questions/3477442/algorithm-efficient-way-to-search-an-integer-in-a-two-dimensional-integer-array">Algorithm: efficient way to search an integer in a two dimensional integer array?</a></p>
  
  <p>This solution is O(2n), which I believed to be the optimal solution. </p>
  
  <p>However, the interviewer then informed me that it is possible to solve this problem in sub linear time. I have racked my brain with how to go about doing this, but I am coming up with nothing.</p>
  
  <p>Is a sub linear solution possible, or is this the optimal solution?</p>