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.