Sorted array A[1...n] and finding out if A[i] = i:

Question: Given a sorted array of distinct integers A[1...n], you want to find out whether there is an index i for which A[i] = i. Give an algorithm that runs in time O(log n).


Answer: Very easy. Just implement a similar algorithm to binary search.


Possible Solution Code (in Python):

 The above code outputs -1 because there is no such i, and 4 since A[4] = 4.