Find Peak Element

Find Peak Element looks like it needs the maximum, but it does not. It teaches a surprising lesson: binary search works on an unsorted array as long as there is a slope to follow. You just have to walk uphill.

The slow way first

The obvious idea: scan left to right and return the first index whose value is bigger than both neighbours. That is O(n) and perfectly correct.

But the question to ask is: can we do better than looking at every element? The array is not sorted, so binary search seems impossible. The trick is that we are not searching for a fixed value — we are searching for a place where the slope turns. And a slope can be probed from the middle.

The idea: always walk uphill

Stand at the middle index mid and compare it to its right neighbour mid + 1.

• If nums[mid] < nums[mid + 1], the ground rises to the right. Keep climbing: a peak must exist somewhere to the right, so move lo = mid + 1.
• Otherwise nums[mid] > nums[mid + 1], the ground falls to the right. The peak is at mid or to the left, so move hi = mid (we keep mid because it might be the peak itself).

Why must this find a peak? Whenever we move toward higher ground, the side we keep still ends in a wall that is taller than its outside edge, so a peak is trapped inside the window. The window halves every step until lo and hi collide on that peak.

Walk through it

Step through the animation. The lo and hi pointers bracket the part still in play, and mid probes the slope. Each compare looks at mid (blue) and mid + 1 (its highlighted right neighbour). The downhill half goes dim and is dropped. The window shrinks [0, 6] → [4, 6] → [4, 5] → [5, 5], where lo meets hi on index 5.

Pseudocode

lo, hi = 0, last index
while lo < hi:                       # stop when the window is one cell
    mid = (lo + hi) // 2
    if nums[mid] < nums[mid + 1]:    # slope rises to the right
        lo = mid + 1                 # a peak is to the right
    else:                            # slope falls to the right
        hi = mid                     # a peak is here or to the left
return lo                            # lo == hi is a peak

The Python solution

def find_peak_element(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

• lo and hi start at the two ends and always keep a peak between them.
• The loop runs while lo < hi — when they meet, the window is a single index and we are done.
• mid = (lo + hi) // 2 rounds down, so mid + 1 is always a valid index inside the window.
• Line 5 reads the slope: if it rises, lo = mid + 1 climbs right; otherwise hi = mid keeps mid as a candidate.
• We never compare against target or assume sortedness — only the local slope matters.

Complexity

We halve the search window on every iteration, so the work is O(log n) with only a couple of pointers — O(1) extra space. That is the whole payoff: an unsorted array, yet a logarithmic search.

When this pattern shows up

Practice