skip to content

In peak finding, when a[mid] < a[mid+1], why is discarding the entire left half safe?

level: middleimportance: must knowfreq 50%

answer

  1. the loop keeps a promise, not an order
  2. what does one rising step guarantee?
  3. a climb inside a finite array must stop
  4. treat both ends as negative infinity
  5. kept range always contains some peak

basics

~20 s

The loop maintains an invariant, not an order: the surviving range always contains a peak. When a[mid] < a[mid+1] the readings rise, and a rising path inside a finite array must reach a local maximum before it runs out.

solid answer

~50 s

The correctness argument is an invariant: *the range `[lo, hi]` always contains at least one local maximum*. It holds at the start, because with the ends treated as negative infinity the whole array must contain one. A rising comparison `a[mid] < a[mid+1]` preserves it on the right side — from `mid+1` the values either climb to `hi` or turn over first, and both cases are peaks. The mirror case preserves it on the left. Since each step shrinks the range and the invariant never breaks, the single index left when `lo == hi` is a peak. Two details carry the proof: the ends must count as peaks, and `a[mid+1]` must exist, which `lo < hi` with a floored midpoint guarantees because it forces `mid < hi`. Note the invariant never claims the discarded half is peak-free — usually it is not.

code

pseudocode · 9 lines
pseudocode
lo = 0
hi = length(a) - 1
while lo < hi:
    mid = floor((lo + hi) / 2)
    if a[mid] < a[mid + 1]:
        lo = mid + 1        // rising here: keep the right side
    else:
        hi = mid            // falling or level: keep mid and the left
return lo                   // a[lo] is at least as large as its neighbours

go deeper

for a junior

Recall the comparison itself — midpoint against its right neighbour — and which way you move on a rise. Knowing that the ends count as peaks is enough at this level.

for a middle

State the invariant as a sentence before touching the code, then show it holds initially, survives both branches, and forces the exit index to be a peak. Include why the probe never reads past the end.

for a senior

Be precise about what the invariant does not claim, and name the mutations that break it: the self-assignment that hangs the loop, and the off-by-one that discards the index the comparison just vindicated.

for a principal

The transferable point is that binary search is an invariant-preservation argument, not a sorted-array trick. Expect to defend that framing when reviewing other bent-precondition searches your team writes.

## The loop under discussion ``` lo = 0 hi = length(a) - 1 while lo < hi: mid = floor((lo + hi) / 2) if a[mid] < a[mid + 1]: lo = mid + 1 else: hi = mid return lo ``` This is the whole method for locating a local maximum in a series of readings that is under no ordering obligation whatsoever. Everything interesting is in why it is correct. ## The invariant State it precisely before saying anything else: > **The closed range `[lo, hi]` always contains at least one local maximum of the array.** **Establishment.** Initially the range is the whole array. Under the convention that the positions just outside the array hold negative infinity, the largest element of any non-empty array is a local maximum, so the invariant holds before the first iteration. **Preservation, rising case.** Suppose `a[mid] < a[mid+1]` and the loop sets `lo = mid + 1`. Consider walking rightward from `mid+1`. Either the values increase all the way to `hi`, in which case `hi` is a peak — it is at least as large as its left neighbour, and its right neighbour is either outside the array or outside the current range but was already excluded by an earlier rising step; or at some index `j` in `(mid, hi]` the climb stops, meaning `a[j] >= a[j+1]` while `a[j] > a[j-1]`, and `j` is a peak. Either way `[mid+1, hi]` contains one. **Preservation, falling-or-level case.** Suppose `a[mid] >= a[mid+1]` and the loop sets `hi = mid`. The symmetric walk leftward from `mid` either climbs to `lo`, which is then a peak, or turns over at some index in `[lo, mid]`. Either way `[lo, mid]` contains one. **Termination.** Each iteration strictly shrinks `hi - lo`: in the rising branch `lo` increases because `mid >= lo`; in the other branch `hi` decreases because `mid < hi`. So the loop ends with `lo == hi`, and by the invariant that single index is a local maximum. ## The stronger statement the invariant does *not* make The most common wrong articulation is "the left half cannot contain a peak". It very often does. A profile that climbs, drops, then climbs higher has peaks on both sides of any midpoint. The invariant is deliberately one-sided: it promises the kept half still has *an* answer, and says nothing about the discarded half. That asymmetry is exactly why the method can only ever promise *a* peak rather than a specific or a maximal one. ## Why `a[mid+1]` is always in range The loop guard is `lo < hi`, and `mid = floor((lo + hi) / 2)` therefore satisfies `lo <= mid < hi`. So `mid + 1 <= hi <= length(a) - 1` and the probe never reads off the end. Change the guard to `lo <= hi` and the same line becomes an out-of-range read on the last iteration — a classic boundary bug that only fires on inputs whose peak sits at the right edge, which is exactly the case a hand-written test tends to omit. The single-element array is worth checking by hand too: the loop body never runs and index `0` is returned, which is correct under the end convention. ## Two mutations that look harmless and are not - **`lo = mid` in the rising branch.** When `hi == lo + 1`, the midpoint floors to `lo`, so `lo = mid` leaves the range unchanged and the loop spins forever. This is the single most common peak-search bug, and it is a termination failure rather than a wrong answer, so it survives casual review. - **`hi = mid - 1` in the falling branch.** The loop still terminates, but it can throw away `mid` itself, which is precisely the index the falling comparison just proved worth keeping. The result is a returned index whose left neighbour is larger — a non-peak. ## Flat runs At termination the invariant chain yields a sharper fact than "a peak": the returned index `i` satisfies `a[i-1] < a[i]` whenever `i > 0` (the only way `lo` ever advances) and `a[i] >= a[i+1]` whenever `i < length(a) - 1` (the only way `hi` ever retreats). So the answer is always a peak under the "at least as large as both neighbours" definition, even when the readings contain flat runs. If the requirement is a *strict* peak — larger than both neighbours — the local probe stops being informative across a plateau, because equal neighbours reveal nothing about which side hides the strict turning point, and the worst case degrades toward a linear scan. That is the same shape of degradation that duplicates inflict on other bent-precondition binary searches, and it is worth naming rather than discovering in production.

  • Why is a[mid+1] never an out-of-range read in that loop?
    Because the guard is `lo < hi` and the midpoint is floored, which forces `lo <= mid < hi`. So `mid + 1` is at most `hi`, itself a valid index. Loosen the guard to `lo <= hi` and the same probe reads one past the end on the final iteration, a bug that only shows up when the peak sits at the right edge.
  • What does the loop return when adjacent samples are equal?
    It still returns a valid peak under the greater-or-equal definition: the exit index satisfies `a[i-1] < a[i]` and `a[i] >= a[i+1]`. If the requirement is a strictly larger value than both neighbours, equal neighbours make the probe uninformative about which side holds one, and the worst case slides toward a linear scan.
  • Someone writes lo = mid instead of lo = mid + 1 in the rising branch. What happens?
    It hangs. Once `hi == lo + 1` the floored midpoint is `lo`, the rising branch reassigns `lo` to itself, and the range stops shrinking. It is a termination bug, not a wrong answer, so small hand-run examples that happen to converge earlier will pass and hide it.

saying these in an interview costs you the question

  • Says the discarded half provably contains no peak
  • Justifies the discard by 'that half is smaller'
  • Proves correctness only for single-humped input
  • Sets lo = mid on a rise, hanging the loop
  • Ignores that the array ends count as peaks

context

resolving links…