Find Peak Element
Walk uphill: binary search on slope direction
Comparing mid to its right neighbor reveals which direction is 'uphill': if the array is rising, a peak MUST exist somewhere further right (the sequence can't rise forever, and even a final rise to the array's edge counts as a peak). If it's falling, a peak must exist at mid or to its left. Either way, half the array can be safely discarded every step — no need to scan for the true global maximum, just any local peak.
Details
Animated on: nums = [1,2,3,1] — return the index of any peak element (strictly greater than both neighbors).
Problem:Find Peak ElementMedium
Pattern:Binary Search on Sorted Data
Walk uphill: binary search on slope direction
step 1 / 6
A peak is any element strictly greater than both neighbors (edges compare against -infinity). Binary search works because you can always walk UPHILL toward a peak — you never need to check every element.
- low=0· arr[0] = 1
- high=3· arr[3] = 1
1FUNCTION findPeakElement(nums):2 low = 0, high = the length of nums - 13 WHILE low < high:4 mid = (low + high) / 2, rounded down5 IF nums[mid] < nums[mid+1]:6 low = mid + 1 (rising, peak is to the right)7 ELSE:8 high = mid (falling, peak is here or to the left)9 RETURN low
← / → step · space play · Home restart
Every step in words
Show all 6 steps
- A peak is any element strictly greater than both neighbors (edges compare against -infinity). Binary search works because you can always walk UPHILL toward a peak — you never need to check every element.
- mid=1 (2) vs mid+1=2 (3).
- 2 < 3: the slope rises to the right, so a peak must exist somewhere in mid+1..high. low = 2.
- mid=2 (3) vs mid+1=3 (1).
- 3 >= 1: the slope falls to the right, so a peak must exist in low..mid (mid itself qualifies). high = 2.
- low and high converged at index 2 (value 3) — a confirmed peak.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.