Suppose that we are given a sorted array of distinct integers A[1, ......, n] and we want to decide whether there is an index i for which A[i] = i. Describe an efficient divide-and-conquer algorithm that solves this problem and explain the time complexity.

1. Describe the steps of your algorithm in plain English. 2. Write a recurrence equation for the runtime complexity. 3. Solve the equation by the master theorem.