Given is an an array A[1..n] of size n of positive integers, and f() a function from positive integers to positive integers that is given by a expensive procedure.

We are also given that f(A[1]) f(A[2]) and f (A[n 1]) f (A[n]).

The goal is to find an index i, 1 < i < n, such that f(A[i]) f(A[i1]) and f (A[i]) f (A[i + 1]) by an algorithm that uses only O(log n) calls to the expensive function f().

For example, if the input is [10,9,5,8,1,11], then correct answers are both 3 and 5.

Present pseudocode, analyze the number of times f() is called, and argue correctness.

can use recurrence relations and the Master theorem to analyze the worst-case number of calls to f() used by your algorithm.