Peak Index in a Mountain Array: Binary Search on Shape

Peak Index in a Mountain Array is LeetCode 852. You are given a mountain array, meaning the values strictly increase up to a single peak and then strictly decrease. Your job is to return the index of that peak. The catch: you need to do it in O(log n) time, which rules out a simple linear scan.

A mountain array arr has three properties: arr.length >= 3, there exists some index i where 0 < i < arr.length - 1 such that arr[0] < arr[1] < ... < arr[i], and arr[i] > arr[i + 1] > ... > arr[arr.length - 1]. In other words, one hump, one peak, no plateaus.

Why this problem matters

Peak index in a mountain array is one of the cleanest introductions to binary search on non-sorted data. The array is not sorted in the traditional sense, but it has a structural property (ascending then descending) that lets you cut the search space in half at every step. Once you see how binary search applies here, problems like Find Peak Element, Find Minimum in Rotated Sorted Array, and Koko Eating Bananas all use the same idea.

The problem also reinforces the distinction between lo < hi and lo <= hi loop conditions, and between hi = mid and hi = mid - 1. These small decisions determine whether your binary search converges correctly or loops forever.

The linear scan approach

The simplest solution is to walk through the array and find where the ascending slope ends:

def peak_index_linear(arr):
    for i in range(1, len(arr)):
        if arr[i] < arr[i - 1]:
            return i - 1
    return -1

This works in O(n) time. You scan from left to right, and the first time a value drops, the previous index was the peak. But the problem explicitly asks for O(log n), so you need binary search.

The key insight: binary search on the slope

You do not need the array to be sorted to use binary search. You just need a way to decide which half of the search space contains the answer. In a mountain array, the slope gives you that decision.

At any index mid, compare arr[mid] to arr[mid + 1]:

• If arr[mid] < arr[mid + 1], you are on the ascending side. The peak must be to the right.
• If arr[mid] > arr[mid + 1], you are on the descending side (or at the peak itself). The peak is at mid or to the left.

Every comparison eliminates half the array. That is the binary search guarantee.

Walking through it step by step

Let's find the peak in [0, 1, 3, 5, 3, 1, 0] using binary search.

Three comparisons and we found the peak at index 3. Out of 7 elements, we never even looked at most of them. That is O(log n) in action.

The binary search solution

Here is the complete Python solution for LeetCode 852:

def peak_index_in_mountain_array(arr):
    lo, hi = 0, len(arr) - 1

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid

    return lo

Let's break this down.

The loop condition is lo < hi. You are narrowing down to a single index, not searching for a target that might be absent. When lo == hi, that index is the peak.

mid = lo + (hi - lo) // 2 avoids integer overflow and always gives a value strictly less than hi when lo < hi. That means mid + 1 is always a valid index, which is important because you access arr[mid + 1].

if arr[mid] < arr[mid + 1] means you are still climbing. The peak is somewhere to the right. Since mid itself is smaller than its right neighbor, it cannot be the peak, so lo = mid + 1 is safe.

else: hi = mid means you are on the downhill side or at the peak. You cannot skip mid because it might be the answer. Setting hi = mid keeps it in the search space.

Complexity analysis

Each iteration cuts the search space in half. The loop runs at most log2(n) times. You use only three variables: lo, hi, and mid. No extra data structures needed.

Building blocks

1. Binary search on non-sorted criteria

Standard binary search compares arr[mid] to a target value to decide which half to keep. This problem replaces that comparison with a structural check: is the slope ascending or descending? The skeleton is identical:

while lo < hi:
    mid = lo + (hi - lo) // 2
    if condition(mid):
        lo = mid + 1
    else:
        hi = mid
return lo

The only thing that changes between problems is the condition. For peak index, it is arr[mid] < arr[mid + 1]. For find minimum in rotated sorted array, it is arr[mid] > arr[hi]. For Koko eating bananas, it is a feasibility check. Same template, different predicate.

2. Slope comparison

The idea of comparing adjacent elements to determine whether you are ascending or descending appears in multiple problems. In Find Peak Element, the same arr[mid] vs arr[mid + 1] comparison works even when there are multiple peaks. In Longest Mountain in Array, slope detection identifies the start, peak, and end of each mountain. The pattern is simple: look at the direction of change, not the absolute values.

Edge cases

• Minimum size array [0, 1, 0]: three elements, peak at index 1. The loop runs once and converges.
• Peak at index 1 [0, 2, 1]: mid = 1, arr[1] > arr[2], so hi = 1. lo == hi == 1, return 1.
• Peak at second-to-last index [1, 3, 5, 2]: the ascending side is longer. Binary search still converges because each step eliminates half the remaining range.
• Large array: with n = 10^6, binary search takes at most 20 comparisons. The linear scan would take up to a million.
• Steep vs. gradual slopes: the algorithm does not care about the magnitude of differences, only whether arr[mid] < arr[mid + 1] or not. Steep and gradual mountains are handled identically.

From understanding to recall

The logic is clean: compare mid to mid + 1, follow the ascending slope, converge when lo equals hi. You get it after one reading.

But in an interview, the small choices trip you up. Was it lo < hi or lo <= hi? Is it hi = mid or hi = mid - 1? Do you compare arr[mid] to arr[mid + 1] or arr[mid - 1]? One wrong decision and the code either skips the answer or loops forever.

Spaced repetition locks these details into long-term memory. You write the solution from scratch today, again in two days, then in a week. By the fourth repetition, while lo < hi and hi = mid are automatic. You are not re-deriving the boundary logic under pressure. You just write it.

LeetCode 852 is an ideal SRS candidate because the code is only six lines but the boundary decisions are subtle. Nail it once in long-term memory, and every binary search variant becomes easier to write correctly.

Related posts

• Find Peak Element - The generalized version where there can be multiple peaks
• Find Minimum in Rotated Sorted Array - Binary search on a non-standard array shape
• Search in Rotated Sorted Array - Binary search with a twist on traditional sorted arrays

CodeBricks breaks peak index in a mountain array into its binary search on slope building block, then drills it with spaced repetition until the template is muscle memory. When a binary search variant shows up in your interview, you do not re-derive the loop bounds. You just write them.