= Solution
Use <minimum search in a rotated distinct array>, then return the cyclic predecessor of the minimum:
``
rotatedMaximum(A):
n = length(A) # require n >= 1
lo = 0
hi = n - 1
while lo < hi:
mid = floor((lo + hi) / 2)
if A[mid] > A[hi]:
lo = mid + 1
else:
hi = mid
return A[(lo + n - 1) mod n]
``
The <loop invariant> says that the minimum index lies in the inclusive interval. If `A[mid] > A[hi]`, the rotation break lies to the right of `mid`; otherwise the segment from `mid` to `hi` is increasing and its indices after `mid` cannot be the minimum. Each update at least halves the interval. Distinct entries make the comparison decisive, including a completely unshifted array. The predecessor of the unique minimum is the maximum, and the one-element case returns that element. The running time is \b[$O(\log n)$], with $O(1)$ auxiliary space.
Back to article page
