Source: Asked in an Amazon interview to a friend
Given an array of size n, x[0 .. n-1] of integers sorted into ascending order with no duplicates, find an array item that is also its index, so that x[i] = i.
For example, x = 3 in the array shown below:
i 0 1 2 3 4 5
x[i] -3 0 1 3 5 7
Your task is to write a program that finds i.
Yes, its a very easy problem, as far as algorithm is concerned. Its here for people preparing for interviews to see if they can write code.