# Find the minimum of a bitonic sequence

A sequence is $a_0,\ldots,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+\log n)$ 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\geq 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 \geq b_y$, $b_y \leq b_z$, but not $b_x=b_y=b_z$. The valley can’t be too large ($|z-x|\leq 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|\geq |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+\log (\frac{n}{m}))=O(m+\log n)$. 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.