The problem
A mountain array strictly increases then strictly decreases. Return the index of the maximum in O(log n).
Stuck? Reveal hints one at a time
How to approach it
- 1While lo < hi: compare arr[mid] with arr[mid + 1].
- 2Rising → the peak is right of mid: lo = mid + 1.
- 3Falling → the peak is mid or left: hi = mid.
- 4Return lo.
Key insight
This is ternary search’s little sibling: with strict unimodality, one comparison of adjacent elements replaces the two probe points.
The solution
Watch out for
- The linear scan passes but defeats the point — say the log n version in interviews.
- On the harder Mountain Array problem (LeetCode 1095), the same routine locates the peak before two directional binary searches.