Consider the problem of taking a sorted array A[1,....,n] of distinct integers, and returning i if there is an element of the array where A[i] = i; if no such element exists then -1 should be returned. For instance, if A ={-2,-1,2,4,8}, then the algorithm should return 4".

Part a: Design an O(log n) decrease-and-conquer algorithm. Give both your pseudocode

and a brief explanation of your algorithm.

Part b: State and solve the recurrence which describes your algorithm's running time.

Show all your work.