Array local maximum
= Array local maximum
{title2=$A_i>A_{i-1},\ A_i>A_{i+1}$}
An entry of a finite <array> which strictly exceeds each existing immediate neighbour. At either endpoint only one neighbour is tested, and the unique entry of a singleton qualifies vacuously. For distinct entries, a <divide-and-conquer algorithm> finds such an entry in $O(\log n)$ time. Maintain an index interval whose left endpoint exceeds the excluded entry immediately to its left, if any, and whose right endpoint exceeds the excluded entry immediately to its right, if any. If a midpoint has a larger internal neighbour, recurse towards it; the comparison supplies the new boundary inequality. Otherwise the midpoint exceeds its internal neighbours and the boundary inequalities cover any external neighbour. Halving the interval and preserving this <recursion invariant> proves correctness and the bound.