Find Peak Element: Binary Search Without a Sorted Array
Solve Find Peak Element in O(log n) with slope binary search: why comparing mid to its right neighbor always works, plus code, a walkthrough, and pitfalls.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Find Peak Element looks like it breaks the one rule everyone knows about binary search: the array must be sorted. The input here is arbitrary — values go up, down, up again — and yet the problem demands an O(log n) answer. That demand is the whole lesson.
What it actually teaches is that binary search never needed sorted input. It needs something weaker: a comparison that tells you, with certainty, which half of the window to throw away. Here that comparison is the local slope — is the array rising or falling at mid? See halving that way and a whole family of problems opens up: rotated arrays, answer-space searches, boundary hunts.
The problem
A peak is an element strictly greater than both of its neighbors. Given an integer array nums, return the index of any peak. Treat the positions just outside the array as negative infinity — nums[-1] = nums[n] = -∞ — so the first or last element can be a peak too. Adjacent elements are never equal, and your solution must run in O(log n) time.
Input: nums = [1, 2, 3, 1]
Output: 2 // nums[2] = 3 is greater than both 2 and 1Three details in that statement do the heavy lifting:
- Any peak is accepted.
[1, 2, 1, 3, 5, 6, 4]has peaks at index 1 and index 5 — either answer passes. - The -∞ boundaries guarantee at least one peak always exists: walk uphill long enough and you must top out, because the array can't rise past its own edge.
- No equal neighbors means every comparison of adjacent elements gives a strict answer — the slope at any point is unambiguously up or down.
The brute force baseline
Scan left to right and return the first index where the array turns downhill.
function findPeakElement(nums) {
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) return i;
}
return nums.length - 1;
}This is correct, and it's worth understanding why: if nums[i] > nums[i + 1] is the first downhill step, then every earlier pair was uphill — so nums[i - 1] < nums[i] — making i a genuine peak. If the loop never fires, the array rises all the way to the end, and the last element (with -∞ beyond it) is the peak.
The catch is the cost: O(n). The problem statement explicitly demands O(log n), which is the interviewer's way of saying "I know the linear scan; show me you can halve." State this baseline in one sentence, then move on.
The key insight: binary search the slope
Stand at any index mid and look one step to the right. There are only two possibilities, and each one guarantees where a peak lives:
nums[mid] < nums[mid + 1]— you're on an ascending slope. Follow it rightward: either the values keep rising until the last index (which is a peak, thanks to the -∞ wall), or they turn downhill somewhere first (and that turning point is a peak). Either way, a peak exists strictly to the right of mid. Discardmidand everything left of it.nums[mid] > nums[mid + 1]— you're on a descending slope, or standing on the peak itself. By the mirror argument, a peak exists at mid or to its left. Discard everything right of mid, but keep mid.
This is the Slope Binary Search pattern. The array isn't sorted, but the slope at mid acts exactly like a sorted-array comparison: it points at a half that is guaranteed to contain an answer. The loop maintains one invariant — the window [left, right] always contains at least one peak — and shrinks the window until a single index remains. That index has nowhere to hide: it must be a peak.
Note that we never claim the discarded half has no peaks — it may have several. We only need one, so "the kept half definitely contains a peak" is all the certainty required.
The optimal solution
var findPeakElement = function(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < nums[mid + 1]) left = mid + 1;
else right = mid;
}
return left;
};Three template details separate this from the classic sorted-array binary search, and each is load-bearing:
while (left < right), not<=. The loop's job is to shrink the window to a single index, not to test a candidate each round. Whenleft === right, the invariant says that index is a peak — return it.right = mid, notmid - 1. When the slope descends,miditself might be the peak. Excluding it can throw away the only peak in the window and break the invariant.nums[mid + 1]is always in bounds. Because the loop only runs whileleft < right, the midpoint satisfiesmid < right, somid + 1 <= right <= nums.length - 1. No boundary check needed.
Termination is also guaranteed: left = mid + 1 moves left strictly up, and right = mid moves right strictly down (since mid < right). The window shrinks every iteration — no infinite loop, even with right = mid.
Walkthrough: nums = [1, 2, 1, 3, 5, 6, 4]
| Step | left | right | mid | Comparison | Slope | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | nums[3]=3 < nums[4]=5 | ascending | left = 4 |
| 2 | 4 | 6 | 5 | nums[5]=6 > nums[6]=4 | descending | right = 5 |
| 3 | 4 | 5 | 4 | nums[4]=5 < nums[5]=6 | ascending | left = 5 |
| 4 | 5 | 5 | — | left === right | — | return 5 |
Three comparisons on a 7-element array, and the window collapses on index 5: nums[5] = 6, flanked by 5 and 4 — a peak. Note that index 1 (value 2, flanked by 1 and 1) is also a peak, and the algorithm never visited it. That's the "any peak" clause at work: the slope walk committed to the right side at step 1 and found a valid answer there.
You can step through it interactively and watch the window shrink comparison by comparison — the slope at each mid is exactly what decides which pointer moves.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Linear scan for first downhill step | O(n) | O(1) | checks each adjacent pair once, worst case walks the whole array |
| Scan for the global maximum | O(n) | O(1) | the global max is always a peak, but finding it can't skip elements |
| Slope binary search | O(log n) | O(1) | one comparison halves the window; ~log₂(n) iterations |
On a 10⁶-element array, the linear approaches do up to a million comparisons; slope binary search does about 20. Same answer, three orders of magnitude less work.
Common mistakes
- Shrinking with
right = mid - 1on a descending slope.midcould be the peak. Kick it out of the window and the invariant "a peak lies in[left, right]" dies — the search can converge on a non-peak. - Writing
while (left <= right)withright = mid. When the window hits one element,mid === left === rightandright = midchanges nothing: infinite loop. Theleft < rightguard and the collapse-to-one-index design go together as a pair. - Comparing against
nums[mid - 1]too. Checking both neighbors invites an out-of-bounds read atmid = 0and adds nothing — the right-neighbor comparison alone decides which half keeps a guaranteed peak. - Hunting the global maximum. The problem asks for a peak, not the biggest one. Insisting on the global max drags you back to O(n), because a maximum can hide anywhere.
- Adding a bounds check for
nums[mid + 1]. Unnecessary, and it signals you haven't traced the loop:left < rightforcesmid < right, somid + 1never leaves the array. (Single-element arrays never enter the loop at all —return lefthands back index 0 directly.)
Where this pattern shows up next
Slope binary search is one member of a family whose shared move is find a comparison that certifies which half to discard:
- Binary Search — the classic sorted-array template this variant descends from; master the
left/right/midmechanics there first. - Guess Number Higher or Lower — the halving decision comes from an oracle's feedback instead of a slope, but the discard logic is identical.
- Sqrt(x) — binary search over an answer space rather than array indices; the "which half is safe" question survives the change of domain.
- Search in Rotated Sorted Array — the hardest version of the same idea: the array is only partially ordered, and each step must first figure out which half is the sorted one.
FAQ
Why does binary search work on an unsorted array in Find Peak Element?
Because binary search doesn't actually require sorted input — it requires a test that certifies one half of the window as safe to discard. Comparing nums[mid] with nums[mid + 1] is that test: an ascending slope guarantees a peak strictly to the right (values must top out before the -∞ boundary), and a descending slope guarantees a peak at mid or to its left. Every comparison halves the window while keeping at least one peak inside it.
What is the time complexity of Find Peak Element?
The slope binary search runs in O(log n) time and O(1) space: each iteration does one comparison and halves the search window, so a million-element array needs roughly 20 iterations. A linear scan is O(n) and also correct, but the problem statement explicitly requires a logarithmic solution — that requirement is the hint to reach for binary search.
What if the array has multiple peaks — which one is returned?
Any peak is a valid answer, and LeetCode's judge accepts all of them. In [1, 2, 1, 3, 5, 6, 4] there are peaks at index 1 and index 5; slope binary search returns 5 because its first comparison sees an ascending slope and commits to the right half. It makes no attempt to find the leftmost peak or the global maximum — only to corner one index that is provably a peak.
Why is the update right = mid instead of right = mid - 1?
When nums[mid] > nums[mid + 1], the slope is descending at mid — meaning mid itself might be the peak. right = mid keeps that candidate inside the window; right = mid - 1 could discard the only peak and let the search converge on a wrong index. The loop still terminates because mid is always strictly less than right, so the window shrinks every time.
Can nums[mid + 1] ever go out of bounds?
No. The loop only runs while left < right, and mid = Math.floor((left + right) / 2) is always strictly less than right in that case, so mid + 1 <= right <= nums.length - 1. Arrays with a single element never enter the loop at all — the function immediately returns index 0, which is correct because both virtual neighbors are negative infinity.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.