PhD Admissions Written Test (Basic)

Question

Let A be a sorted array of distinct integers of length n. Design an algorithm to find an index i such that A[i] = i if such an index exists. If there are more than one such indices, you may output any one. If no such index exists then the algorithm outputs −1. The asymptotic time complexity of the fastest algorithm for this problem, assuming the array is already available, is Θ ______________________________

Comments

Binary Search would help. In worst case, running time is $\Theta(\log n)$ and in best case, it is $\Theta(1).$