162. Find Peak Element Medium

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Approach

Input: An integer array nums

Output: Return the index of any peak element

This problem belongs to the Binary Search on Peak category.

We can use binary search to quickly locate the position of a peak. Every time, we compare mid with the next element mid + 1.

If it is greater than the next element, it means the peak might be at the current position or somewhere to the left of the current position. Thus, we narrow the search interval down to [left, mid].

If it is less than the next element, it means the peak must strictly lie to the right of the current position. Thus, we narrow the search interval down to [mid + 1, right].

Eventually, we will always converge to a state where left == right == Peak Element, and at that point, returning either left or right yields the correct element.

Implementation

python

from typing import List

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # Initialize the left and right pointers
        left, right = 0, len(nums) - 1

        # Binary search
        while left < right:
            mid = (left + right) // 2  # Get the mid position

            # Check if the element at mid is strictly greater than the element to its right
            if nums[mid] > nums[mid + 1]:
                # If so, the peak is on the left (including mid)
                right = mid
            else:
                # Otherwise, the peak must be strictly on the right
                left = mid + 1

        # Finally when left == right, we have found the peak index
        return left

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2); 

        if (nums[mid] > nums[mid + 1]) {
            right = mid
        } else {
            left = mid + 1;
        }
    }

    return left;
};

Complexity Analysis

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

Links

162. Find Peak Element (English)162. 寻找峰值 (Chinese)