Find Bitonic Peak

In this lesson, we will be given an array that is bitonically sorted, an array that starts off with increasing terms and then concludes with decreasing terms. In any such sequence, there is a “peak” element which is the largest element in the sequence. We will be writing a solution to help us find the peak element of a bitonic sequence.

A bitonic sequence is a sequence of integers such that: $x_0 < ... < x_k > ... > x_{n-1}$ for some $k$, 0 <= $k$ < $n$

Notice that the sequence for this problem does not contain any duplicates.

For example:

    1, 2, 3, 4, 5, 4, 3, 2, 1

is a bitonic sequence. In the example above, the peak element is 5.

We assume that a “peak” element will always exist.

Let’s look at some other examples.