Find Peak Element

medium binary search

Problem

A peak element is an element that is strictly greater than its neighbors. Given an 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.

Inputnums = [1, 4, 3, 5, 2]

Output1 or 3

Index 1 (value 4) and index 3 (value 5) are both peaks; either is acceptable.

nums (comma-separated, no two adjacent equal)

def find_peak_element(nums):
    l, r = 0, len(nums) - 1
    while l < r:
        m = (l + r) // 2
        if nums[m] < nums[m + 1]:
            l = m + 1
        else:
            r = m
    return l

function findPeakElement(nums) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const m = (l + r) >> 1;
    if (nums[m] < nums[m + 1]) l = m + 1;
    else r = m;
  }
  return l;
}

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (nums[m] < nums[m + 1]) l = m + 1;
            else r = m;
        }
        return l;
    }
}

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

Explanation

A peak is any element bigger than both neighbours, and we only need to find one. The surprising part is that binary search works here even though the array is not sorted — the trick is to always walk uphill.

At each step we compare nums[m] with its right neighbour nums[m + 1]. If nums[m] < nums[m + 1], the slope is rising, so a peak must exist somewhere to the right — we set l = m + 1. Otherwise the slope is flat-or-falling, so a peak sits at m or to its left, and we set r = m.

Because we always move toward higher ground, and the array edges act like valleys, the window is guaranteed to close in on a peak. When l == r, that index is a peak and we return l.

Example: nums = [1,4,3,5,2]. With m = 2, nums[2]=3 < nums[3]=5, so we go right. The window narrows to index 3 (value 5), a valid peak. (Index 1 is also a peak; any one is acceptable.)

Each step halves the search range, so this finds a peak in O(log n) time.

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