Given a sorted array of distinct integers A1n you want to fi

Given a sorted array of distinct integers A[1,...,n], you want to find out whether there is an index i for which A[i] = i. Design an O(logn) time algorithm, and show your analysis.

Solution

Here, we can scan traverse the entire array and check for the constraint but in worst case, the algorithm will take O(N) time. So, we can think of something different. Since the array is sorted, we can apply binary search whose average time complexity is O(log N).

Pseudo code (returns -1 if index is not found else return the index):

find_index(A, low, high):

    if (low > high) return -1

    else:

        mid = floor((high+low) / 2)

        if (A[mid] > mid):

            return find_index(A, low, mid-1)

        else:

            return find_index(A, mid+1, high)