Find Peak Element — Binary Search on Slope

The Problem

You are given an array nums where nums[i] != nums[i+1] for all valid i, and nums[-1] and nums[n] are treated as negative infinity. Return the index of any peak — an element strictly greater than its neighbors. The required complexity is O(log n).

The strict-inequality and infinity-sentinel rules guarantee at least one peak exists. The O(log n) hint says binary search, but the array isn’t sorted, so we need a different invariant.

Intuition

Maintain a range [lo, hi] that is guaranteed to contain a peak. At each step look at the slope between nums[mid] and nums[mid + 1]. If the slope goes up, the right side must contain a peak (continue ascending and you eventually hit the negative-infinity sentinel past the array, so a peak exists in (mid, hi]). If the slope goes down, the same argument applied leftward says a peak exists in [lo, mid]. Either way we halve the range and preserve the invariant, so the loop terminates with lo == hi on a peak.

Explanation with Example

Take nums = [1, 2, 1, 3, 5, 6, 4].

index:  0  1  2  3  4  5  6
value:  1  2  1  3  5  6  4

lo=0 hi=6  mid=3  nums[3]=3 < nums[4]=5 -> uphill -> lo=4
lo=4 hi=6  mid=5  nums[5]=6 > nums[6]=4 -> downhill -> hi=5
lo=4 hi=5  mid=4  nums[4]=5 < nums[5]=6 -> uphill -> lo=5
lo=5 hi=5  return 5  (value 6, a peak)

The other peak at index 1 (value 2) is also valid, but binary search converges on the right one in this run.

Code

The loop terminates when lo == hi, which must be a peak by induction on the invariant.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

class Solution {
    public int findPeakElement(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < nums[mid + 1]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

#include <vector>
using namespace std;

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int lo = 0, hi = (int)nums.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < nums[mid + 1]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
};

Edge Cases

A single-element array returns 0; that element is trivially a peak against negative-infinity sentinels on both sides. A strictly increasing array returns the last index. A strictly decreasing array returns 0. An array with multiple peaks returns any one of them.

There are no off-by-one errors as long as you compare with nums[mid + 1], which is safe because mid < hi implies mid + 1 <= hi < len(nums).

Complexity Analysis

Time is O(log n): the range shrinks by half each iteration. Space is O(1): just two indices.

Notice the algorithm works on an arbitrary array (not sorted), which is unusual for binary search. The trick is that the invariant is about the existence of a peak in the current range, not about value ordering.

How to Explain It in an Interview

Lead with the invariant: “I maintain a range [lo, hi] that must contain a peak. At each step, I look at the slope between nums[mid] and nums[mid + 1]. If the slope goes up, a peak must exist on the right side (or at the rightmost element, which is greater than the implicit negative infinity beyond the array). If it goes down, a peak must exist at or before mid.”

Walk through a small ascending-then-descending example like [1, 3, 2]. Finish with O(log n) and O(1).

If the interviewer asks why a peak must exist, point to the discrete intermediate-value argument: a function on integers that starts going up and is finite-valued must eventually plateau or descend, and at the transition you have a peak.

Related Problems

• Peak Index in a Mountain Array — guaranteed unimodal.
• Find in Mountain Array — same shape, find a target.
• Search in Rotated Sorted Array — binary search on a structural property.
• Find Minimum in Rotated Sorted Array — dual problem (find a valley).