Find Peak Element [Medium] — Binary Search on Slope

Problem Statement

A peak element is greater than its neighbors. Given nums, return the index of any peak element. Assume nums[-1] = nums[n] = -∞. O(log n) required.

Input: [1,2,3,1] → Output: 2
Input: [1,2,1,3,5,6,4] → Output: 5 or 1

Intuition

Binary search: if nums[mid] < nums[mid+1], there's a peak to the right; otherwise, there's a peak at mid or to the left.

Solutions

C++

int findPeakElement(vector<int>& nums) {
    int lo=0, hi=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;
}

Java

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;
}

JavaScript

var findPeakElement = function(nums) {
    let lo=0, hi=nums.length-1;
    while (lo<hi) {
        const mid=lo+(hi-lo>>1);
        if (nums[mid]<nums[mid+1]) lo=mid+1;
        else hi=mid;
    }
    return lo;
};

Python

def findPeakElement(nums: list[int]) -> int:
    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

Complexity

Time: O(log n)
Space: O(1)