Find Peak Element
Find any peak in an unsorted array in O(log n) by binary searching on the slope: go right while rising, left while falling.
Problem Understanding
Find Peak Element: a peak is an element strictly greater than its neighbours. Given an array nums where no two neighbours are equal, return the index of any peak, treating nums[-1] and nums[n] as −∞. The solution must run in O(log n).
Example: [1, 2, 1, 3, 5, 6, 4] returns 1 or 5; both are peaks.
The Intuition: Walk Uphill
Stand at mid and look at mid + 1:
- Rising (
nums[mid] < nums[mid + 1]): keep walking uphill to the right. The climb must stop somewhere, at worst at the last element, because past the end is −∞. So a peak lies in[mid + 1, hi]. - Falling:
miditself may be the top, or a peak is further left. So a peak lies in[lo, mid].
Each comparison halves the range, so this is binary search without a sorted array: what matters is that one half is guaranteed to hold an answer. The same idea of searching by a condition instead of a value drives Find Minimum in Rotated Sorted Array.
Interactive Walkthrough
Each value is a bar, so the slope at mid is easy to see. mid is filled, its right neighbour is outlined, and the range [lo, hi] is tinted. Try Only rising, where the peak is the last element.
Dry Run Table
Input: nums = [1, 2, 1, 3, 5, 6, 4]
| lo | hi | mid | nums[mid] vs nums[mid+1] | Move |
|---|---|---|---|---|
| 0 | 6 | 3 | 3 < 5 (rising) | lo = 4 |
| 4 | 6 | 5 | 6 > 4 (falling) | hi = 5 |
| 4 | 5 | 4 | 5 < 6 (rising) | lo = 5 |
lo = hi = 5. Answer: 5 (nums[5] = 6).
The Solution Template
Binary search on the slope with lo < hi, so mid + 1 is always in range.
Find Peak Element Code
1var findPeakElement = function(nums) {2 let lo = 0, hi = nums.length - 1;3 while (lo < hi) {4 const mid = Math.floor((lo + hi) / 2);5 if (nums[mid] < nums[mid + 1]) lo = mid + 1;6 else hi = mid;7 }8 return lo;9};
Edge Cases & Common Mistakes
- One element: it is a peak; the loop does not run and index 0 is returned.
- Strictly increasing: the last index is the peak, since
nums[n]counts as −∞. - Strictly decreasing: index 0 is the peak.
- Using
lo <= hi: thenmid + 1can go out of range andhi = midcan loop forever; uselo < hi. - A linear scan: finds a peak in O(n), but the problem requires O(log n).
Summary
While lo < hi, compare nums[mid] with nums[mid + 1]: if it is rising, a peak is to the right (lo = mid + 1); otherwise a peak is at mid or to its left (hi = mid). When lo meets hi, return it. O(log n) time and O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet