An SRE board plots per-minute p99 latency. On-call needs any local spike so they can pin a flamegraph to that minute — not the global worst in the week, just a ridge taller than both neighbors. The first version walked every sample and compared it to the cells on each side. A few hundred minutes returned instantly. After a week of one-second ticks, the board was still scanning when the incident window closed.

Find Peak Element asks for any index taller than both neighbors. An array already gives a[i] for free. A scan uses that and still pays O(n). The array is not globally sorted. The license to discard a half is the slope at mid, not a target sitting in a sorted slice.

This is an interview writeup, not a procedure lecture. The binary search post owns the invariant and mid overflow. The membership writeup is the sorted cousin: discard the half that cannot hold a key. Here there is no key. We only ask whether mid is climbing, and walk toward a ridge that must exist.

The problem

Given a non-empty int[] nums, return any index i such that nums[i] is strictly greater than its neighbors. Treat slots outside the array as negative infinity: index 0 is a peak if it beats nums[1], and index n - 1 is a peak if it beats nums[n - 2]. Adjacent values are unique. Typical interviews want O(log n) time.

nums = [4, 8, 3, 2, 9, 7]  →  1   (8; index 4 is also a peak)
nums = [6, 4, 2]           →  0
nums = [2, 5, 9]           →  2
nums = [11]                →  0

Note: A strictly increasing run peaks at the last index; a strictly decreasing run peaks at the first. That is the -∞ rule, not a special case. Do not hunt for the global maximum unless they asked for it. Any local ridge satisfies the prompt.

Linear neighbor checks are the honest brute force

Every index is compared to the cells that exist beside it. Correct. Linear.

int findPeakScan(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        boolean leftOk = (i == 0) || nums[i] > nums[i - 1];
        boolean rightOk = (i == n - 1) || nums[i] > nums[i + 1];
        if (leftOk && rightOk) {
            return i;
        }
    }
    throw new IllegalStateException("no peak");
}

At n = 20 this is a rounding error. At a week of one-second samples you paid a full walk for a question a slope answers in a handful of probes: is mid still climbing?

Binary search the slope, not a target

Keep inclusive ends, but stop when one slot remains: while (lo < hi). Mid is lo + (hi - lo) / 2. Look at nums[mid] versus nums[mid + 1] — that pair is always in range while lo < hi.

  • If nums[mid] < nums[mid + 1], you are on an ascent. A peak sits strictly right of mid: either the climb stops at a local max, or it runs to the last index (a peak under -∞). Set lo = mid + 1.
  • Otherwise you are on a descent. Mid itself may be the ridge, or a peak sits left of it. Set hi = mid. Do not drop mid.

lo == hi is a peak index. Return it. You never needed the whole array sorted — only that an ascent guarantees a ridge on that side.

nums = [4, 8, 3, 2, 9, 7]
        0  1  2  3  4  5

lo=0 hi=5 mid=2  3>2  descent  → hi=2
lo=0 hi=2 mid=1  8>3  descent  → hi=1
lo=0 hi=1 mid=0  4<8  ascent   → lo=1
lo=1 hi=1  done — return 1 (value 8)

Index 4 (9) is also a peak. The loop did not promise it. Either index is legal.

The Java is that loop:

int findPeakElement(int[] nums) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

Time is O(log n) — each comparison throws away half the remaining range. Space is O(1) — two indices, no extra table. Mid overflow already lives on the algorithms post; do not re-lecture it unless they ask.

Note: Use while (lo < hi) and keep hi = mid. Mid is still a candidate. Membership’s inclusive while (lo <= hi) must drop mid on every miss; copying hi = mid onto that contract never terminates when lo == hi. There is no target to equal.

What interviewers usually poke next

  • All peaks. Log time finds one. Listing every ridge is a scan; say so.
  • Adjacent equals. A flat slope does not tell you which side holds a strict peak. Shrinking by one is honest and worst-case linear. The unique-neighbors license is gone; say so.
  • Global maximum. The global max is a peak. This loop does not promise it — only a local one.
  • Empty / null. The prompt promised a non-empty array. In production you would reject; at the board, ask.

You are done with this problem when you can say, out loud, why the neighbor scan is correct, why an ascent licenses discarding the left half on an unsorted array, and why hi = mid on the descent branch.