Find Peak Element — Binary Search on Slope

Problem 319 · Find Peak Element

Difficulty: Medium · Pattern: Peak Binary Search

A peak is an element greater than its neighbors. Return any peak index.

Intuition

If nums[mid] < nums[mid+1], peak is to the right (uphill). Otherwise peak is to the left (or at mid).

Solutions

# Python
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  # uphill to right
        else: hi = mid                             # uphill to left (or mid is peak)
    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;
}

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

Complexity

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