Finding an element in array, whose index number and element value same Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?



I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?
If the array had $A[i]=i, \forall{i}$, then the complexity would have been $\theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't. 

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.  

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$. 

The algorithm to find such element is mere a slight modification of binary search where you update low &amp; high based on $i&lt;A[i]$ - if it's true update high=mid-1 else if $i&gt;A[i]$ update low=mid+1.  The complexity is indeed $\theta(log_2n)$