title: Finding an element in partially sorted array
body: <p>I had a following interview question.</p>
  
  <p>There is an array of nxn elements. The array is partially sorted i.e the biggest element in row <code>i</code> is smaller than the smallest element in row <code>i+1</code>.
  How can you find a given element with complexity O(n)</p>
  
  <p>Here is my take on this:</p>
  
  <p>You should go to the row n/2.And start compare for example you search for 100 and the first number you see is 110 so you know it's either in this row or in rows above now you go n/4 and so on.</p>
  
  <p>From the comments</p>
  
  <blockquote>
    <p>Isn't it O(n * log n) in total? He has
    to parse through every row that he
    reaches per binary search, therefore
    the number of linear searches is
    multiplied with the number of rows he
    will have to scan in average. – Martin
    Matysiak 5 mins ago.</p>
  </blockquote>
  
  <p>I am not sure that is a right solution. Does anyone have something better</p>