Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms/5/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Functional programming, design and analysis of algorithms 5 b Solution by
Codex 0 2026-10-31
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 , with auxiliary space. New to topics? Read the docs here!