There's no target and the array isn't sorted. But the local slope always points toward higher ground — and uphill has to end in a summit somewhere.
A peak is strictly greater than its left and right neighbors. In [1,2,3,1], index 2 (value 3) is a
peak. You may return any peak, and the ends count too — imagine nums[-1] = nums[n] = −∞,
so a rising or falling edge still qualifies. That guarantees every array has at least one peak.
A linear scan finds one in O(n), but the required O(log n) forces binary search — on an
unsorted array.
There's no target to compare against, so inspect the local shape instead: nums[mid] vs
nums[mid+1]. That single comparison reveals a slope, and the slope proves which side must contain a
peak.
−∞ past the edge. Either way, the right half
holds a peak.
You can't see the whole range, only whether the next step is up or down. Always stepping uphill guarantees you reach a summit — maybe not the tallest, but a real one.
Toss a ball; it rolls to a low point. Invert that — walk toward the rising side and you're funneled to a high point. The slope does the navigating.
Binary search may throw away a half that contains a peak — that's fine. It only has to keep at least one, not all of them.
Set an array, then step. Each step marks mid (with its right neighbor dashed), reads the slope, and discards a half — the live range stays full-color, discarded bars fade. When one bar remains it locks in as a peak (teal).
Try 1 2 3 4 5 (all uphill → last index) or
5 4 3 2 1 (all downhill → index 0). Multiple peaks? Any one is a valid answer.
| left | mid | right | nums[mid] | nums[mid+1] | Slope | Action |
|---|---|---|---|---|---|---|
| 0 | 3 | 6 | 3 | 5 | up | left = 4 |
| 4 | 5 | 6 | 6 | 4 | down | right = 5 |
| 4 | 4 | 5 | 5 | 6 | up | left = 5 |
Loop ends with left = right = 5 → peak at index 5 (value 6). This array has two peaks (indices 1
and 5); the search converged on one, which is all the problem asks.
int findPeakElement(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < nums[mid + 1]) lo = mid + 1; // uphill → right else hi = mid; // downhill → keep mid, left } return lo; }
lo == hi, a single index remains — and the invariant says it's a peak.lo < hi, mid never equals hi, so
mid+1 stays in bounds — no edge checks.
O(log n) time, O(1) space. The interval shrinks every step (left jumps past mid, or right drops to mid), so it always terminates.
[left, right] always contains at least one peak. It's true at the start (the whole array has one),
and each slope decision keeps a half that provably still contains one. When the range narrows to a single index,
that index must be a peak.
This leans on a liberating idea: binary search doesn't need to preserve every valid answer, only at least one. An array can have several peaks; discarding a half that happens to hold one is fine as long as the kept half is guaranteed to hold another.
On a downhill, mid itself can be the peak ([1,3,2]). Dropping it discards the
answer — use right = mid.
Comparing mid−1 and mid+1 works but needs edge guards for index 0 and n−1. The
one-sided slope test needs none.
The global max is a peak, but finding it is O(n) and sorting is O(n log n). You only need a local peak — cheaper.
The array can zigzag (1 3 2 5 4 8 6) with many peaks. The slope proof still guarantees one on
the kept side.
This is the strongest break from "binary search = sorted array + target." Here there's no target and no global order — just a local slope that reliably points toward a valid answer. That's enough to halve the space. The same directional idea powers mountain-array peaks, bitonic arrays, and unimodal-function optimization.
The unifying definition: binary search is any method that repeatedly proves one half can't be the answer and throws it away — sortedness is just the most familiar way to earn that proof.