Find Peak Element

Approach Summary

If arr[mid] < arr[mid+1], a peak exists to the right. Otherwise, it exists to the left or mid is a peak.

Full Solution & Approach

A peak is an element strictly greater than both neighbors, and the problem guarantees at least one exists. The insight is that if nums[mid] < nums[mid + 1], the array is strictly rising at mid, so a peak must exist somewhere to the right — you can discard the entire left half and still not miss one. If nums[mid] > nums[mid + 1], the array is falling at mid, so a peak exists at or to the left of mid. Each comparison eliminates half the range, giving O(log n). The proof relies on the boundaries: beyond the ends the values are treated as negative infinity, so any monotonic run must terminate in a peak. This is a different flavor of binary search — instead of finding a target value, you find a local extremum by tracking the slope direction.

Each step halves the search range — O(log n) time. Constant space — O(1).

Solution Code

Solution

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

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

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

int findPeakElement(const 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;
}

Edge Cases to Watch

Monotonically increasing array — the peak is the last element
Monotonically decreasing array — the peak is the first element
Single element — it is a peak by definition
Multiple peaks — any valid one is accepted

How to Recognize This Pattern

Find any peak element in O(log n)

Complexity Analysis

Time Complexity

O(log n)

Space Complexity

O(1)