252. Find a Peak
A peak is an element strictly greater than both of its neighbours. The ends count as peaks if they beat their single neighbour.
Print the index of ANY peak. Adjacent values are guaranteed to differ, so a peak always exists.
A linear scan is O(n) and obvious. The interesting answer is O(log n),
and it works even though the array is not sorted at all.
Look at the midpoint. If a[mid] < a[mid+1] then the values are rising to the
right, and a rising sequence must eventually stop rising, either at the end of
the array or at a peak. So a peak is guaranteed to exist on that side, and you
can discard the other half without knowing anything else.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - `a[i] != a[i+1]` for every valid `i`
Input
The first line contains an integer n.
The second line contains n integers, with no two adjacent values equal.
Output
Print one integer, the 0-based index of any peak.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.