Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 5 / d

Maintain an inclusive interval $[lo,hi]$ with these recursion invariants: if $lo>0$, then $A[lo]>A[lo-1]$; if $hi<n-1$, then $A[hi]>A[hi+1]$. The original full interval satisfies both conditions vacuously.In the left-recursion branch, the new right endpoint satisfies $A[m-1]>A[m]$ and the old left boundary is retained. The right-recursion branch is symmetric. Thus both recursion invariants persist.

If neither branch is taken, $A[m]$ exceeds its neighbours within the current interval because all entries are distinct. If $m$ is an endpoint of that interval and there is a neighbour outside, the boundary recursion invariant supplies the missing strict inequality. Hence the returned index is an array local maximum with respect to the original array, not just the restricted interval. Every branch shortens the interval, so termination is guaranteed; this also establishes existence, including the singleton case.

Each call performs at most two comparisons, and a recursive interval has at most half as many elements, up to rounding. Thus $T(n)\le T(\lceil n/2\rceil )+O(1)$ andThe conventional bound is $O(\log n)$ for $n\ge 2$, with constant work for a singleton. Distinctness is essential to this proof of a strict local maximum.