Find Peak Element
How to find A local maximum in an unsorted array in O(log n) — not the biggest value overall, just one that beats both its neighbors.
The job
You have an array of numbers with no ordering guarantee. Find the index of ANY "peak" — a value that is not smaller than either of its immediate neighbors.
The obvious way
Scan left to right, checking every value against both its neighbors.A list of 1,000,000 can cost 1,000,000 checks — surprising, since the array is not even sorted.
The idea
Compare the middle value to the one right after it. If it is smaller, the slope is going uphill, and following uphill is GUARANTEED to reach a peak — so the peak is somewhere to the right. Otherwise, the slope has stopped climbing right here, so mid itself qualifies as a peak candidate and everything strictly to its right can be dropped.
Think of it like this. Hiking in fog with no map, trying to reach any hilltop. At every step you only need to know whether the ground ahead of you is rising or falling — always walk uphill, and you are mathematically guaranteed to reach a peak, without ever needing to see the whole mountain range at once.
Climbing toward any peak
4 numbers, no order required. A "peak" is any value not smaller than both its neighbors — find one.
def find_peak(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = mid
return loThis run
Peak found at index 2, value 3 — found in 2 looksinstead of scanning all 4.
Why this works on an unsorted array
Slope, not sortedness
The only thing being compared is mid to its immediate neighbor — a purely LOCAL fact. Global sortedness was never required.
Uphill always leads somewhere
Treating the array's edges as negative infinity guarantees that walking uphill must eventually stop rising — and the point where it stops is a peak, by definition.
Any peak, not the biggest
The problem only asks for A peak. Two-Peaks presets show this clearly — different runs can legitimately converge on different valid answers.
How to spot this shape
The tell: You need any index satisfying a LOCAL comparison to its neighbor(s), and following the direction that comparison points is guaranteed to reach a valid answer.
Reach for it when
- The problem asks for "a" peak/valley/local extremum, not "the" global one.
- The array has no sortedness guarantee at all.
- A single comparison between mid and an adjacent element tells you which half to keep.
- The array's edges are implicitly treated as extreme (negative or positive infinity).
Not this when
- You need the GLOBAL maximum or minimum — that needs a full scan, since no local rule finds it in log time.
- You need every peak, not just one.
- Ties or plateaus make "strictly uphill" ambiguous in a way the problem cares about.
Practice
6 problemsThe lesson, exactly. Compare mid to mid+1: uphill means a peak is to the right, flat-or-downhill means mid could be it.
A guaranteed single peak (strictly up then strictly down) — the exact same search, with a friendlier guarantee.
The same "keep mid, compare to a neighbor/endpoint" shape, hunting a valley's rotation point instead of a peak — its own lesson here too.
Find the peak first with this exact search, then binary search each of the two monotonic halves for the target.
The 2D generalization: binary search columns, and within each candidate column find the row maximum to decide which way to move.
A different property entirely (a balanced partition point), but the same halve-based-on-a-local-comparison instinct.