Find Peak Element: Binary Search Without Sorted Input

"Find Peak Element" shows up again and again in Google, Meta, Uber phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Modified Binary Search pattern quickly and code it cleanly. Part 6 of 11 in the Modified Binary Search arc.

The Problem

A peak element is strictly greater than its neighbors. Given nums where adjacent elements differ and virtual boundaries are negative infinity, return the index of any peak in O(log n). The eye-opener: binary search on a completely unsorted array.

Input:  nums = [1, 2, 1, 3, 5, 6, 4]
Output: 5 (value 6) — index 1 (value 2) is an equally valid answer.

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

Sortedness was never the requirement — a directional guarantee is. Comparing mid with its right neighbor tells you which side must contain a peak: an ascending edge cannot descend forever without peaking, because the boundary is negative infinity. Any-answer problems often hide this structure.

The Approach

If nums[mid] is less than nums[mid + 1], you are on an ascent — a peak exists at mid + 1 or beyond, so lo = mid + 1. Otherwise mid is on a descent or is itself a peak, so hi = mid. The range collapses onto some peak.

The argument is an induction on the slope, and interviewers will ask for it: walking uphill with an infinite cliff at the end must summit somewhere. Two sentences, delivered before the code.

Python Solution

def find_peak_element(nums: list[int]) -> int:
    """Index of any element strictly greater than its neighbors."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1               # ascending: a peak lies right
        else:
            hi = mid                   # descending or at peak: keep mid
    return lo

Complexity

• Time: O(log n) — halving on the slope predicate
• Space: O(1) — two indices

Interview Tips and Follow-Ups

• mid + 1 is always in range because the loop maintains lo strictly below hi — pre-verify rather than defend it after a crash.
• The 2D version (Find a Peak Element II) binary-searches on rows with a column max — a genuine Google follow-up.
• Articulate why 'any peak' (not 'the max') is what makes O(log n) possible — the global max genuinely requires O(n).

If this clicked, continue the Modified Binary Search arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.