An array A[1..n], has the following property: It first in- creases upto some point and then starts decreasing after this point.

So for some number i, A[j] < A[j + 1] for all j < i and A[j] > A[j + 1] for all j i. This means that A[i] is the maximum entry in the array. But we dont know this number i. The problem is to find this maxi- mum entry.

Give an algorithm for this task which takes O(log n) time. Explain it in english as well as write a pseudocode. Give its analysis in terms of big-O complexity.