Find the minimum of a bitonic sequence
A sequence is 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 time, where 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 such that for and for all . We only have to find one local minima in any consecutive subsequence of length . This time we partition a interval into 4 pieces.
We define a valley to be 3 points such that , , but not . The valley can’t be too large (). 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 , pick the midpoint between and , and consider the relations. , then we have an valley . , then we have an valley , if , consider the midpoint of and to be . If , we know at least of the values are the same, and do a linear search between and . Otherwise, we must have (draw it and see why) and this is a new valley!
If we have , something similar to above can be done.
It’s easy to see the recursion gets us . So the only problem comes from how do we find the first valley that contains the local minima. Let If , then is a valley. If , then is a valley. So we pick 3 possible that is apart, and either one of them allow us to construct a valley, or at least 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.