Find Peak Element: Why Binary Search Works on an Unsorted Array

Find Peak Element is a favorite interview question because it breaks a rule most candidates have memorized: "binary search needs a sorted array." The array here is not sorted, yet the expected answer runs in O(log n). If you can explain why, you show the interviewer you understand binary search as a technique for shrinking a search space, not just a trick for sorted lists.

The problem

You get an array nums where no two neighbors are equal. A peak is an element strictly greater than its neighbors. Treat nums[-1] and nums[n] as negative infinity. Return the index of any peak.

The linear answer (say it first)

Walk left to right and return the first i where nums[i] > nums[i+1]. If you never find one, the last index is a peak. This is O(n) and correct, and stating it in one sentence buys you credibility before you optimize.

def find_peak_linear(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i
    return len(nums) - 1

The key observation

Look at any middle index mid and compare it with mid + 1.

That is the whole invariant: the current window always contains at least one peak. Every comparison throws away half the window while keeping that promise true.

The O(log n) solution

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1      # peak is to the right
        else:
            hi = mid          # mid could be the peak
    return lo

Notice two details interviewers watch for. First, the loop is lo < hi, not lo <= hi, so mid + 1 is always in range. Second, the else branch sets hi = mid, not mid - 1, because mid itself might be the answer. When lo == hi, the window has one element and the invariant says it is a peak.

How to explain it out loud

  1. State the linear scan and its cost.
  2. Say: "I don't need sorted order, I need a rule that tells me which half still contains an answer."
  3. Describe the slope argument with the negative-infinity boundaries.
  4. Write the loop and point out the lo < hi and hi = mid choices.
  5. Test on [1, 2, 3, 1] (returns 2) and [1, 2, 1, 3, 5, 6, 4] (returns 1 or 5, both valid).

Common follow-ups

The pattern to remember is "binary search on a monotonic property," and it shows up again in Search in Rotated Sorted Array, Koko Eating Bananas and minimum-capacity problems.


Disclosure: I work on Linkjob AI. If you want live practice talking through problems like this, you can try it free.