30 views
Let $A$ be a sorted array containing $n$ distinct integers, such that, for all $1 \leq i<j \leq n$, we have $A[i]<A[j]$. Note that the integers stored in the array $A$ are not necessarily from the set $\{1, \ldots, n\}$. Design an algorithm that outputs an index $i \in\{1, \ldots, n\}$ such that $A[i]=i$, if such an $i$ exists, and outputs $-1$ otherwise. The worst case running time of the algorithm should be asymptotically better than $O(n)$. Prove the correctness of your algorithm and state its asymptotic time complexity.