A bitonic array is an array A such that there is some index i, where the values in A are increasing from index 1 to i, and decreasing from index i to the end of the array. Design a divide?and?conquer algorithm to find the maximum element in a bitonic array. Analyze its running time with the Master Theorem.

Hint: This is very simple to binary search. You want to nd the point where the array stops increasing and starts decreasing. How can you tell whether that is to the left or right of your current location?