$2.(20$ points$)$ You are given an input array A consisting of n distinct integers. Assume that

the array A is sorted in increasing order. Design an algorithm that determines if there is an

index i such that A$[$i$]=$ i$.$ Give a divide and conquer algorithm to solve this problem. Write

the recurrence relation describing the runtime of the algorithm and give the solution to the

recurrence. You do not need to show your work for deriving the solution to the recurrence.

Your will receive zero credit if you do not use divide$-$and$-$conquer.