A simple algorithm to find if Array[i] = i

Given a sorted array A of n integers. We have to find whether there exists an array index i such that A[i] = i.
This problem seems like an ideal candidate for a divide and conquer strategy. As the array is already sorted, we first check whether the number stored at the middle of the array is same as the middle index. If so we have found our answer, otherwise we check if it is larger than or smaller than the middle index value. If it is larger, that means all the indices following it would store numbers larger than them, so there is no point in checking them out. Similarly if it is smaller, this indicates that all indices smaller than middle would not satisfy the problem constraints. Depending on the condition, we reject either the low half or the high half of the array, effectively halving the candidate pool.  We continue to do so till either we exhaust the array completely or we find a successful match. This algorithm runs in logarithmic time or formally its run time complexity is governed by O(log n)

Output:
Index found at 2

Leave a Reply