Lets say you are given a sorted array A of length n(sorted from smallest to largest). Assume that all the elements of A are integers and that they are distinct (no duplicates). Note that the integers in A can be negative. Your goal is to find an index such thatA[i] = i, or output no solution if no such index exists. (If there are multiple for whichA[i] = i, you only have to return one of them.)

Give pseudocode for a recursive algorithm for the above problem that runs in O(log(n)) times. You should also justify that the algorithm is correct and state the recurrence formula for your algorithm.