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
Walkthrough:nums = [1, 2, 1, 3, 5, 6, 4]
Every frame checks the slope one step to the right of mid — uphill pushes the window right, downhill pulls it left, toward whichever peak is closest.
0
1
1
2
2
1
3
3
mid
4
5
5
6
6
4
left=0, right=6, mid=3 → nums[3]=3 < nums[4]=5. Uphill; peak is right. left = mid+1 = 4
0
1
1
2
2
1
3
3
4
5
5
6
mid
6
4
left=4, right=6, mid=5 → nums[5]=6 > nums[6]=4. Downhill; peak is at or left of mid. right = mid = 5
0
1
1
2
2
1
3
3
4
5
mid
5
6
6
4
left=4, right=5, mid=4 → nums[4]=5 < nums[5]=6. Uphill; peak is right. left = mid+1 = 5
0
1
1
2
2
1
3
3
4
5
5
6
6
4
left=5 = right=5: loop ends. nums[5]=6 is greater than both neighbors — a peak.

Final Answer: 5

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