Let A[1 . . . n] be an array of n distinct integers. We say that A is peaked, if there exists an index 1 k n such that:

(1) For all 1 i < k, A[i] < A[i + 1] and (2) for all k < i n, A[i 1] > A[i]. That is, the array increases until k and decreases afterward. Call the index k the peak of A.

Describe an algorithm which in O(log n) time finds the peak of a given peaked array A[1 . . . n] consisting of n distinct integers. Specifically, give short descriptions of how your algorithm works, why it is correct, and why it achieves the stated running time.