title: Interview question - Search in sorted array X for index i such that X[i] = i
body: <p>I was asked the following question in my interview yesterday:</p>
  
  <p>Consider a Java or C++ array say <code>X</code> which is sorted and no two elements in it are same. How best can you find an index say <code>i</code> such that element at that index is also <code>i</code>. That is <code>X[i] = i</code>.</p>
  
  <p>As clarification she also gave me an example:</p>
  
  <pre><code>Array X : -3 -1 0 3 5 7
  index   :  0  1 2 3 4 5
  
  Answer is 3 as X[3] = 3.
  </code></pre>
  
  <p>The best I could think was a linear search. After the interview I though a lot on this problem but could not find any better solution. My argument is: the element with the required property can be anywhere in the array. So it could also be at the very end of the array so we need to check every element.</p>
  
  <p>I just wanted to confirm from the community here that I'm right. Please tell me I'm right :)</p>