Algorithm

Find Peak Element

Binary Search Pattern

Find Peak Element

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.

CONSTRAINTS
  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums[i] != nums[i+1] for all valid i
EXAMPLE 1
Input: nums = [1,2,3,1]
Output: 2
3 at index 2 is greater than both neighbors 2 and 1.
EXAMPLE 2
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Index 5 (value 6) is a peak.
What if the peak is at the edge?
The problem treats indices outside the array as negative infinity. So an element at index 0 is a peak if it's larger than index 1.

Finding a peak element is interesting because the array is unsorted. Usually, unsorted data requires a linear scan.

The Brute Force Walk

You can just walk the array from index 0 (O(N)). If you ever see a number that is smaller than the one you just passed, you've found a peak. This works perfectly fine but takes linear time.

The Hill Climber Discovery

Discover: We can find a peak in O(log N) time by treating the array like a mountain range and becoming a "Hill Climber."

1. Pick any spot (the midpoint).
2. Look at the Slope: Look at your neighbor to the right.
3. Go Uphill:
- If the right neighbor is TALLER, you are on an "Upward Slope." Since the array eventually ends at negative infinity, there MUST be a peak somewhere to your right.
- If the right neighbor is SHORTER, you are on a "Downward Slope." A peak must exist right where you are, or somewhere to your left.

By always following the upward slope, you are mathematically guaranteed to land on a peak.

Code Blueprint
text
left = 0
right = length - 1

WHILE left < right:
    mid = left + (right - left) / 2
    
    // Check the slope to the right
    IF nums[mid] < nums[mid + 1]:
        // Uphill slope! Peak is to the right
        left = mid + 1
    ELSE:
        // Downhill slope! Peak is at or to the left
        right = mid

RETURN left
Why the Pattern is King

Find Peak Element is the best example of how Binary Search can work on Unsorted data as long as there is a Monotone Trend. Even though the whole array isn't sorted, the "Upward Slope" property is something we can exploit to throw away half the mountain range at every step. This turns a slow climb into a logarithmic jump.

Interactive Strategy Visualization

Hill Climbing Strategy

To find a peak, we just need to follow the slope upwards. If the right neighbor is higher, we climb right. Otherwise, the peak is to the left (or we are on it).

1Left
2
1
3
5
6
4Right
🔭
Scanning Mountain Range...

O(N) linear scan
→
O(log N) binary search