Find Peak Element

Problem Statement

A peak element is strictly greater than its neighbours. Given nums where nums[-1] = nums[n] = -∞, return the index of any peak, in O(log n).

Example

Input:  nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: 6 (index 5) is a peak (index 1 would also be valid).

Approach

If nums[mid] < nums[mid+1], a peak must exist on the right (the slope rises), so go right. Otherwise a peak is at mid or to its left, so go left. The window shrinks to a single peak.

Complexity

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

Solution Code

Python

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

Java

int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) left = mid + 1;
        else right = mid;
    }
    return left;
}

C++

int findPeakElement(vector<int>& nums) {
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) left = mid + 1;
        else right = mid;
    }
    return left;
}

Key Takeaways

• Binary search works even though the array is not sorted — the slope is monotone enough.
• Following the ascending side guarantees you walk uphill to a peak.
• Reference: LeetCode 162 (Find Peak Element).