Find Peak

A peak element is one strictly greater than its neighbours (positions off the ends count as −∞). Given an array where no two adjacent values are equal, return the index of a peak in O(log n). For the test inputs here there is exactly one peak.

findPeak(nums)

Input format: space-separated integers (non-empty).

Examples

[1, 3, 2]         // → 1
[1, 2, 3, 1]      // → 2
[5, 4, 3, 2, 1]   // → 0

Walkthrough

Thinking it through

A peak is a local maximum — bigger than both neighbors. There could be several scattered through the array, and you only need any one. The array isn't sorted, so binary search seems out of reach — but binary search only needs a way to look at a middle position and confidently discard one side as guaranteed not to contain the answer, while the other side is guaranteed to still have it.

Finding the guarantee: follow the uphill slope

Compare the middle to its right neighbor:

Middle smaller than its right neighbor: the sequence is rising. Somewhere along that rise, values must eventually stop increasing — turning downward (a peak right there) or rising all the way to the last element (a peak by definition, since off-the-end counts as −∞). Either way, a peak is guaranteed strictly right of the middle — discard the middle and everything left.
Middle greater than or equal: the sequence is flat or falling. The middle already beats its right neighbor, so if it also beats its left (or is the first element), it's already a peak. Otherwise walking left must eventually hit a rise-then-fall or the start — a peak guaranteed at or left of the middle. Discard everything right of the middle, keeping the middle as a candidate.

Why this is a valid invariant

At every step, the current range [lo, hi] is guaranteed to contain at least one peak — that's what justifies discarding half each time.

Why this converges and why it beats scanning

Each comparison halves the range while preserving that guarantee, so it shrinks to a single index in time proportional to the array's logarithm. A linear scan checking every element's neighbors takes time proportional to the array's length; this needs only local slope information — a rise must eventually crest, a fall must have come from somewhere.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.