Find Peak Element

Problem

An element of an integer array is a peak if it is strictly greater than its immediate neighbours. Treat the positions just outside the array as negative infinity, so the first element is a peak if it exceeds the second, and the last element is a peak if it exceeds the second-to-last. Given an array nums in which no two adjacent elements are equal, return the index of any one peak in logarithmic time.

• nums has between 1 and 100,000 elements.
• Values fit in a signed 32-bit integer.
• No two adjacent elements are equal.

Examples

• nums = [4, 7, 12, 8] → 2, since 12 is greater than both 7 and 8.
• nums = [3, 9, 2, 6, 11, 14, 10] → 1 or 5; both index 1 (value 9) and index 5 (value 14) are peaks and either is accepted.
• nums = [9, 6, 2] → 0. The first element is a peak because its left neighbour counts as negative infinity.

Hints

1. A single pass comparing each element to the next is O(n). The problem says a peak always exists; why is that true?
2. Look at the middle element and its right neighbour. If the array is going uphill there, what do you know about the right half?
3. Binary search that keeps the half in which a peak is guaranteed: move right when nums[mid] < nums[mid + 1], otherwise keep mid in the window.