ISI 2019 | PCB CS | Question: 1

Question

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.

Answer 1

I think basic binary search should work ,
If A[i] is greater than "i" then we will move to left otherwise mid index would be the answer because anyway we are not going to have any case where element is less than the index it belongs as the array is distinct and sorted.
Time complexity : log(size_of_array)