Peak Index in a Mountain Array: Binary Search Without a Sorted Array

Most people learn binary search as "the fast way to find a value in a sorted array" — and then freeze the first time an interviewer hands them an array that isn't sorted. Peak Index in a Mountain Array is the problem that breaks that mental block.

A mountain array climbs strictly up, hits one peak, and falls strictly down. It is not sorted. And yet binary search solves it in O(log n), because binary search never needed sortedness — it needs a question whose answer flips exactly once across the array. Learn to spot that flip, and a whole family of problems (rotated arrays, boundary searches, "search on the answer") collapses into one template.

The problem#

An array arr is a mountain if it has at least 3 elements, strictly increases to some index i, and strictly decreases after it. Given a mountain array, return the index of the peak — the i where arr[i] is the maximum. The follow-up demands O(log n) time.

Two guarantees in the statement do a lot of quiet work:

• The slopes are strict — no plateaus, no equal neighbors. Every comparison between adjacent elements gives a definitive answer.
• There is exactly one peak, and it is never at index 0 or n - 1 (both slopes must exist).

The brute force baseline#

Walk from the left until the array stops climbing. The first index whose next element is smaller is the peak.

This is O(n), and honestly it passes: 10⁵ elements is nothing for a linear scan. So why bother beating it? Because the follow-up explicitly asks for O(log n), and because this problem exists to test one thing: do you know binary search works on more than sorted arrays? Answering with a linear scan tells the interviewer you don't. The same reasoning applies to arr.indexOf(Math.max(...arr)) — correct, O(n), and it dodges the entire point.

The key insight: binary search the slope, not the value#

You are not searching for a value. You are searching for a turning point — the index where the array switches from climbing to falling. So ask a different question at each index:

Evaluate that predicate across any mountain array and you get a clean pattern:

Every index on the ascent answers false; every index from the peak onward answers true. One flip, no exceptions — the strict slopes guarantee it. The peak is simply the first index where the predicate is true.

That FFFTT shape is the entire requirement for binary search. Check the middle: if arr[mid] < arr[mid + 1], you're still on the ascent, so the peak lies strictly to the right — discard mid and everything left of it. Otherwise you're at or past the peak — discard everything right of mid, but keep mid itself, because it might be the answer. Either way, half the candidates vanish per comparison.

This is the mountain peak binary search pattern, a special case of find-the-first-true — the same skeleton behind lower-bound searches and First Bad Version.

The optimal solution#

This is exactly the algorithm the visualizer steps through:

Three details make this template correct, and each one is load-bearing:

• while (left < right), not <=. The loop maintains the invariant the peak is always inside [left, right]. It stops the moment the window shrinks to one index — which must be the peak.
• left = mid + 1 on the ascent. arr[mid] < arr[mid + 1] proves mid itself cannot be the peak (its right neighbor is bigger), so it's safe to exclude it.
• right = mid, not mid - 1, on the descent. arr[mid] > arr[mid + 1] proves the peak is at mid or earlier — excluding mid here could throw away the answer.

Notice there's no early-return arr[mid] === target check anywhere. Boundary-style binary search doesn't hunt for a match; it squeezes the window until only the answer remains.

Walkthrough: arr = [0, 1, 3, 5, 4, 2]#

Three comparisons on six elements, and the window [left, right] never once excluded the true peak. Step 3 is the one worth staring at: mid = 3 is the peak, and right = mid keeps it alive while right = mid - 1 would have destroyed it. You can step through it interactively and watch the window collapse comparison by comparison.

Complexity#

On 10⁵ elements the binary search finishes in ~17 comparisons instead of up to 10⁵. Space is constant either way — just two pointers.

Common mistakes#

• Writing right = mid - 1 on the descending branch. When mid is the peak itself, the comparison arr[mid] > arr[mid + 1] is true — and mid - 1 skips the answer. right = mid is the contract: the descending case only proves the peak is at or before mid.
• Using while (left <= right) with right = mid. Once left === right, mid === left and the descending branch sets right = mid — nothing changes, and the loop spins forever. The < condition and right = mid are a matched pair; don't mix templates.
• Fearing arr[mid + 1] goes out of bounds. It can't. Inside the loop left < right, so mid < right ≤ n - 1, which means mid + 1 ≤ n - 1. The template protects itself.
• Comparing against arr[mid - 1] instead. Now mid = 0 does go out of bounds, and you need extra edge handling. The forward comparison is the clean one.
• Returning arr[left] instead of left. The problem asks for the peak's index, not its value. Easy to fumble after solving value-returning cousins of this problem.

Where this pattern shows up next#

Predicate-based binary search — find where a condition flips — is one of the highest-leverage templates in interviews:

• Binary Search — the classic sorted-array version; master its invariants before bending them.
• Guess Number Higher or Lower — the same halving logic driven by an oracle's feedback instead of array reads.
• Sqrt(x) — binary search over an answer range where the predicate is mid * mid <= x, no array at all.
• Search in Rotated Sorted Array — another "not sorted, still binary-searchable" array, where you reason about which half is orderly.

FAQ#

Why does binary search work on a mountain array if it isn't sorted?#

Because binary search doesn't require a sorted array — it requires a predicate that is monotonic over the index range. In a mountain array, the test arr[i] > arr[i + 1] is false for every index on the ascent and true from the peak onward: it flips exactly once. That single flip lets each comparison discard half the remaining indices with certainty, which is all binary search ever needed. Sortedness is just the most familiar way to get such a predicate.

What is the time complexity of Peak Index in a Mountain Array?#

The slope-based binary search runs in O(log n) time and O(1) space: each iteration performs one comparison and halves the window [left, right], so ~17 iterations cover an array of 10⁵ elements. A linear scan or indexOf(Math.max(...arr)) is O(n) — accepted by the judge, but it misses the follow-up requirement and the point of the problem.

Why is it right = mid and not right = mid - 1?#

When arr[mid] > arr[mid + 1], you only know you're on the descending slope — which includes the possibility that mid is the peak. Setting right = mid - 1 could discard the answer. By contrast, when arr[mid] < arr[mid + 1], index mid is provably not the peak (its neighbor is bigger), so left = mid + 1 is safe. The asymmetry between the two moves mirrors the asymmetry in what each comparison proves.

Can arr[mid + 1] ever be out of bounds?#

No. The loop condition left < right guarantees mid = floor((left + right) / 2) is strictly less than right, and right never exceeds n - 1. Therefore mid + 1 ≤ n - 1 on every iteration. This is a built-in advantage of the left < right template — comparing against arr[mid - 1] instead would need explicit edge handling at index 0.

How is this different from Find Peak Element?#

Find Peak Element (LeetCode 162) allows arbitrary arrays with multiple local peaks and only guarantees that neighbors differ; you may return any peak. Peak Index in a Mountain Array guarantees exactly one peak with strictly monotonic slopes on both sides. Remarkably, both use the identical loop — compare arr[mid] with arr[mid + 1] and walk toward the larger side — but the mountain guarantee makes the correctness argument simpler: there is only one turning point the search can converge to.