Binary Search — Find Peak Element
↗ LeetCode: Find Peak Element · Medium · pattern chapter →
A peak is an element strictly greater than its neighbors. Given nums (with nums[-1] = nums[n] = -∞), return the index of any peak. Must run in O(log n).
Example 1 — nums = [1,2,3,1] → 2 (value 3 is a peak) Example 2 — nums = [1,2,1,3,5,6,4] → 1 or 5 (both are peaks) Example 3 — nums = [1] → 0
Constraints — 1 ≤ n ≤ 1000; -2³¹ ≤ nums[i] ≤ 2³¹ − 1; adjacent values differ (no plateau). Brute linear scan is O(n) = 10³ ops one-off; but with 10⁶ streaming queries per hour that's 10⁹ ops (dead). Binary search on the "climb toward the higher neighbour" invariant is O(log n) ≈ 10 comparisons per query.
Interview timer00:00
Approach 1 — Linear scan
O(n). Rejected.
Approach 2 — Binary search on slope
Intuition. Compare nums[mid] with nums[mid+1]:
- If
nums[mid] < nums[mid+1], the slope is climbing → a peak must be atmid+1or to its right (sincenums[n] = -∞, some right neighbor must eventually drop). - Else, the slope is falling → peak at
midor to its left.
Why it works. The invariant is: at least one peak exists in [lo, hi]. Each step preserves that invariant by choosing the half that includes a rising boundary going down.
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;
else hi = mid;
}
return lo;
}Complexity — Time O(log n); Space O(1).
Approach 3 — Find global max (for the "any peak" spec, wasteful)
O(n) linear pass; rejected.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Linear scan | O(n) | O(1) | rejected |
| BS on slope | O(log n) | O(1) | expected |
When to use which
- Any peak → BS on slope.
- All peaks → linear pass.
- "Peak in 2D matrix" → recurse on rows/cols, similar BS idea (LC 1901).
- "Peak with plateau" → strict inequality assumption fails; problem becomes harder.
Related problems
- Find Minimum in Rotated Sorted Array — similar BS on non-monotone
- Peak Index in a Mountain Array — guaranteed single peak
- Find a Peak Element II — 2D