Unimodal

Exercise 2.9

A sequence of integers A = (a_1, \dots , a_n) of length n \geq 3 is called unimodal if there exists an index t with 1\leq t\leq n such that a_1 <a_2 <\dots<a_t and a_t >a_{t+1} >\dots> a_n. In other words, the sequence A increases up to a_t and then decreases. The element a_t is called its top.

Write a divide and conquer algorithm that, given a vector that stores a unimodal sequence, finds its top in cost O(\log n).

The Great Wave off Kanagawa
Katsushika Hokusai

Argue that the suggested algorithm has cost O(\log n), and prove its correctness.

Extra

What if you didn’t want to find the top t but to tell whether an element x is in the unimodal sequence?

After doing this exercise, you might want to solve the Jutge problem X82938 Search in a unimodal vector.