# Find the minimum of a bitonic sequence

A sequence is $a_{0},…,a_{n−1}$ is
*bitonic* if it is a circular shift of a first non-increasing
then non-decreasing sequence.

Find an algorithm that can find the minimum value in the sequence in $O(m+gn)$ time, where $m$ is the maximum number of repeats for a single element. This problem is a generalization of a previous problem.

A trick about circular shift of an sequence is to consider the sequence as a periodic sequence. Create sequence $b$ such that $b_{i}=a_{i}$ for $i<n$ and $b_{i+n}=b_{i}$ for all $i≥n$. We only have to find one local minima in any consecutive subsequence of length $n$. This time we partition a interval into 4 pieces.

We define a valley to be 3 points $x<y<z$ such that $b_{x}≥b_{y}$, $b_{y}≤b_{z}$, but not $b_{x}=b_{y}=b_{z}$. The valley can’t be too large ($∣z−x∣≤n$). If we have such an valley and this valley contains a local minima, then it is easy to create a smaller (3/4 of the original size) valley that also contain the local minima.

If $∣y−x∣≥∣z−y∣$, pick the midpoint $w$ between $x$ and $y$, and consider the relations. $w<y$, then we have an valley $(x,w,y)$. $w>y$, then we have an valley $(w,y,z)$, if $b_{w}=b_{y}$, consider the midpoint of $w$ and $y$ to be $u$. If $b_{w}=b_{u}=b_{y}$, we know at least $1/8$ of the values are the same, and do a linear search between $x$ and $z$. Otherwise, we must have $b_{w}>b_{u}<b_{y}$(draw it and see why) and this is a new valley!

If we have $∣y−x∣<∣z−y∣$, something similar to above can be done.

It’s easy to see the recursion gets us $O(m+g(mn ))=O(m+gn)$. So the only problem comes from how do we find the first valley that contains the local minima. Let $0<k<n$ If $b_{0}>b_{k}$, then $b_{0},b_{k},b_{n}$ is a valley. If $b_{0}<b_{k}$, then $b_{k},b_{n},b_{k+n}$ is a valley. So we pick 3 possible $k$ that is $n/4$ apart, and either one of them allow us to construct a valley, or at least $n/4$ of the points have the same value, and we use linear search.

This algorithm is basically the simplified version of the algorithm in Boris Veroy’s paper that can handles repeats.