= Minimum search in a rotated distinct array
In a nonempty rotation of a strictly increasing <array>, keep an inclusive interval containing its minimum. Compare its midpoint with its right endpoint. If the midpoint is larger, the minimum lies strictly to the right of the midpoint; otherwise the midpoint-to-right segment is increasing and the minimum lies at or left of the midpoint. The interval at least halves until one index remains. The cyclic predecessor of this minimum holds the maximum, so both extrema are found with $O(\log n)$ comparisons. Distinctness makes the two-way comparison decisive.
Back to article page
