Find Peak Element: Binary Search on Slope

Find Peak Element is LeetCode 162, and it is one of the clearest examples of binary search working on something that is not sorted. There is no sorted array here. Instead, you are searching based on slope: is the array going up or going down at the midpoint? Follow the uphill direction, and you will always land on a peak. That is the whole trick.

If you have solved Find Minimum in Rotated Sorted Array or Koko Eating Bananas, you already know that binary search is not limited to sorted data. It works whenever you can split the search space in half using a yes/no condition. For find peak element, that condition is the slope.

The problem

You are given an integer array nums where nums[i] != nums[i + 1] for all valid i. A peak element is one that is strictly greater than its neighbors. You need to return the index of any peak element. The algorithm must run in O(log n) time.

The problem also defines nums[-1] = nums[n] = -infinity, meaning the boundaries are treated as negative infinity. So if the array is strictly increasing, the last element is a peak. If it is strictly decreasing, the first element is a peak.

Example: nums = [1, 2, 3, 1]. The peak is at index 2 (value 3), because 3 > 2 and 3 > 1.

The line chart makes it obvious: a peak is where the slope flips from ascending to descending. Binary search finds that flip point in O(log n).

Why binary search works here

This is the part that surprises people. The array is not sorted. How can binary search possibly apply?

The key insight comes from the boundary condition. Since nums[-1] and nums[n] are both negative infinity, if you stand at any index and the array is going up to your right, there must be a peak somewhere to the right. Either the array keeps going up and the last element is a peak (because it drops to negative infinity), or it turns downward at some point, creating a peak there.

The same logic works in reverse. If the array is going down to the right of mid, there must be a peak at mid or to its left.

So at each step, you check one comparison: is nums[mid] less than nums[mid + 1]?

• Yes, ascending slope: a peak must exist to the right. Set lo = mid + 1.
• No, descending slope (or equal, but the problem guarantees no ties): a peak is at mid or to the left. Set hi = mid.

You throw out half the search space every time. That is O(log n).

Visual walkthrough

Let's find a peak in [1, 2, 1, 3, 5, 6, 4] step by step.

Three real comparisons. Out of 7 elements, we found the peak at index 5 in O(log n) time. We never even looked at most of the array.

The code

Here is the complete Python solution for LeetCode 162, find peak element:

def find_peak_element(nums):
    lo, hi = 0, len(nums) - 1

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

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

    return lo

Let's break this down.

The loop condition is lo < hi, not lo <= hi. We are narrowing down to a single index, not searching for a target that might not exist. When lo == hi, that index is our answer.

mid = lo + (hi - lo) // 2 is the standard overflow-safe midpoint. When lo < hi, mid is always strictly less than hi, so mid + 1 is always a valid index. That is important because we access nums[mid + 1].

if nums[mid] < nums[mid + 1] means mid is on an ascending slope. A peak exists 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 mid is on a descending slope (or it is the peak). We cannot skip mid because it might be the answer, so we set hi = mid, not mid - 1.

Why not compare to both neighbors?

You might be tempted to check whether nums[mid] is greater than both nums[mid - 1] and nums[mid + 1], and return early if it is. That works, but it is unnecessary. The lo < hi approach converges to the peak without ever needing a two-sided comparison. The code stays simpler and the logic stays clean.

The single comparison nums[mid] vs nums[mid + 1] is enough to decide which half to keep. Trust the invariant: as long as you follow the ascending slope, the search space always contains at least one peak.

Complexity analysis

Time: O(log n). Each step cuts the search space in half. The loop runs at most log2(n) times.

Space: O(1). Three variables: lo, hi, mid. No extra data structures.

This is optimal. You cannot guarantee finding a peak in fewer than O(log n) comparisons.

Edge cases to watch for

• Single element: nums = [1]. lo == hi from the start, so the loop never runs. Return 0.
• Two elements: nums = [1, 2]. mid = 0, nums[0] < nums[1], so lo = 1. Now lo == hi, return 1.
• Strictly increasing: nums = [1, 2, 3, 4]. Binary search keeps going right because the slope is always ascending. Converges on index 3 (the last element). The boundary condition nums[n] = -infinity makes this a peak.
• Strictly decreasing: nums = [4, 3, 2, 1]. Binary search keeps going left because every mid is on a descending slope. Converges on index 0.
• Multiple peaks: nums = [1, 3, 2, 4, 1]. Both index 1 and index 3 are peaks. The algorithm returns whichever one the binary search path happens to find. The problem only asks for any peak, so this is correct.

The building blocks

This problem is built on one core building block: binary-search-template.

The skeleton is exactly the standard binary search: maintain [lo, hi], compute mid, eliminate half the range. The only twist is the decision logic. Instead of comparing nums[mid] to a target, you compare nums[mid] to nums[mid + 1] to decide which direction leads uphill.

# Standard binary search (find target):
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1

# Find peak element:
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] < nums[mid + 1]:
        lo = mid + 1
    else:
        hi = mid

Same structure, different comparison. If you can write the binary search template from memory, find peak element is just plugging in a new condition.

This "binary search on a property" pattern shows up in several related problems:

• Find Minimum in Rotated Sorted Array (LeetCode 153): compare mid to hi to find the rotation pivot
• Koko Eating Bananas (LeetCode 875): binary search on the answer space with a feasibility check
• Search in Rotated Sorted Array (LeetCode 33): decide which half is sorted, then check if the target is in that half

From understanding to recall

The logic is simple enough to grasp in one reading: compare mid to mid + 1, follow the ascending slope, converge. You get it.

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

Spaced repetition fixes this. You type the solution from scratch today, again tomorrow, then in three days. By the fourth repetition, the while lo < hi and hi = mid pattern is muscle memory. You are not re-deriving it under time pressure. You just know.

LeetCode 162 is a perfect SRS candidate because the code is short (six lines) but the boundary decisions are subtle. Nail it once in long-term memory, and every binary search variant gets easier.

Related posts

• Find Minimum in Rotated Sorted Array (LeetCode 153): Binary Search on the Pivot - Another problem where binary search works on unsorted data by comparing mid to its boundary
• Koko Eating Bananas (LeetCode 875): Binary Search on the Answer - Binary search applied to a range of possible answers instead of an array