= Solution
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.
``
LocalMaximum(A):
require length(A) >= 1
return Peak(0, length(A)-1)
Peak(lo, hi):
m = floor((lo+hi)/2)
if m > lo and A[m-1] > A[m]:
return Peak(lo, m-1)
if m < hi and A[m+1] > A[m]:
return Peak(m+1, hi)
return m
``
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 \b[<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)\leq T(\lceil n/2\rceil)+O(1)$ and
$$
\boxed{T(n)=O(1+\log n)}.
$$
The conventional bound is $O(\log n)$ for $n\geq2$, with constant work for a singleton. Distinctness is essential to this proof of a strict local maximum.
Back to article page
