Find Peak Element: Binary Search on an Unsorted Array

Find peak element is the problem that breaks the rule most people learn first: binary search needs sorted input. Here the array is not sorted, the answer is required in O(log n), and binary search still works. The reason is worth understanding, because it is the real idea behind binary search: you do not need order, you need a test that tells you which half still contains an answer.

The problem it solves

A peak is an element that is at least as high as its neighbours. Positions outside the array count as lower than anything, so the first and last elements only have one neighbour to beat. Given an array, return the index of any peak.

For [1, 3, 6, 4, 2] the only peak is index 2, the 6. For [1, 2, 1, 3, 5, 6, 4] both index 1 and index 5 are peaks, and either answer is accepted. Every non-empty array has at least one peak: the maximum is always one.

A linear scan finds a peak in O(n): walk right until the next value is lower. The common interview version asks for O(log n), which rules the scan out.

The intuition

Stand at mid and look one step to the right.

• The ground rises, nums[mid] < nums[mid + 1]. Keep walking right from mid + 1. Either the values keep rising all the way to the last element, and the last element is a peak because the edge counts as lower, or they turn down somewhere, and the top of that turn is a peak. Either way, a peak exists in the right part. The left part, including mid, can go.
• The ground falls or stays level, nums[mid] >= nums[mid + 1]. Walk left from mid and the same argument runs in reverse: a peak exists at mid or to its left. mid itself may be that peak, so it stays in the range.

Each test throws away half of the range and keeps at least one peak inside what is left. When the range shrinks to one index, that index is a peak. Put more precisely, the loop keeps two facts true: the value just left of lo is lower than nums[lo], and nums[hi] is at least the value just right of it. When lo and hi meet, one index satisfies both.

Notice what the search does not promise: it returns a peak, not the highest one, and not a particular one. Finding the global maximum still needs a full scan.

Watch it run

The animation uses [1, 3, 6, 4, 2]. It starts by pointing out that the row is not sorted, and it does not need to be. The range is 0 to 4 and mid is 2: 6 then 4, the ground falls, so mid itself may be the peak. Keep it, and the range becomes 0 to 2. Now mid is 1: 3 then 6, the ground rises, so a peak must lie to the right, and the range becomes 2 to 2. The range has closed on index 2, and 6 really is higher than both of its neighbours. Two comparisons for five values.

The code

The lesson's search, with a step counter:

def find_peak(nums):
    lo, hi, steps = 0, len(nums) - 1, 0
    while lo < hi:
        mid = (lo + hi) // 2
        steps += 1
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1                 # uphill: a peak sits to the right
        else:
            hi = mid                     # downhill or level: mid may be the peak
    return lo, steps

print(find_peak([1, 3, 6, 4, 2]))                   # (2, 2)
print(find_peak([1, 2, 1, 3, 5, 6, 4]))             # (5, 3)
print(find_peak([7]), find_peak([1, 2, 3]), find_peak([3, 2, 1]))
# (0, 0) (2, 1) (0, 2)

The tempting bug is hi = mid - 1, which throws away the one index the falling step did not rule out:

def wrong(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 - 1                 # discards mid, which may be the peak
    return lo

print(wrong([1, 3, 6, 4, 2]))                       # 1   3 is not a peak

Against a brute-force peak test on 5,000 random arrays, including repeated values, and checking the step count stays logarithmic:

import math
import random

def is_peak(nums, i):
    left = nums[i - 1] if i > 0 else float("-inf")
    right = nums[i + 1] if i + 1 < len(nums) else float("-inf")
    return nums[i] >= left and nums[i] >= right

random.seed(18)
ok = True
for _ in range(5000):
    nums = [random.randint(0, 6) for _ in range(random.randint(1, 40))]
    i, steps = find_peak(nums)
    ok &= is_peak(nums, i)
    ok &= steps <= math.ceil(math.log2(len(nums)))
print(ok)                                           # True

The complexity

• Time: O(log n). Each comparison halves the range, so there are at most about log₂ n steps.
• Space: O(1). Three indices.
• The linear scan is O(n) and simpler, and it is the right answer if the question does not ask for better.
• The global maximum cannot be found faster than O(n) on unsorted data: any value you skip could be the largest.

Where it goes wrong

• Using hi = mid - 1. A falling step to the right says nothing against mid, and the bug above returns a non-peak.
• Writing while lo <= hi with hi = mid. When lo == hi the range never shrinks and the loop does not end.
• Comparing with mid - 1 instead of mid + 1. It can work, but only with the rounding flipped to (lo + hi + 1) // 2; mixing the two reads outside the array or loops forever.
• Assuming a strict peak exists. With equal neighbours, as in [2, 2, 2], no element is strictly greater than both. Many versions of the problem rule this out by saying adjacent values differ; the "at least as high" definition always has an answer.
• Promising the highest peak. The search finds some peak, not the tallest.

When it shows up in interviews

It is a classic medium, often used to check whether a candidate understands binary search or just remembers it for sorted arrays. Expect the follow-up "why is it correct on unsorted data?", and be ready to state the invariant. Related questions reuse the same slope test: the peak of a mountain array, the minimum of a rotated sorted array, and a two-dimensional peak, where you binary search on columns and take each column's maximum.

How to say it in an interview

"I binary search on the slope, not on the values. At mid I compare with the next element. If it goes up, a peak must exist to the right, because the values either climb to the end or turn down somewhere, so I set lo to mid + 1. Otherwise mid or something to its left is a peak, and mid might be the one, so I set hi to mid. The range always contains a peak, and when it shrinks to one index, that index is the answer. O(log n) time and O(1) space. It returns a peak, not the highest one."

The same idea of keeping the half that must contain an answer drives binary search on the answer and search in a rotated sorted array.