Find the minimum of a bitonic sequence

A sequence is $a_0,\dots ,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\ge 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\ge b_y$, $b_y\le b_z$, but not $b_x=b_y=b_z$. The valley can’t be too large ($|z-x|\le 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|\ge |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.