Peak Finding & Bitonic Arrays

## What "peak" means here A local maximum — a peak — in a one-dimensional series is an index `i` whose value is at least as large as its immediate neighbours: `a[i] >= a[i-1]` and `a[i] >= a[i+1]`. The two ends need a convention: treat the positions just outside the array as holding negative infinity, so index `0` counts as a peak whenever `a[0] >= a[1]`, and the last index counts whenever it is at least as large as the one before it. Without that convention a strictly rising series of altitude samples would contain no peak at all and the search would have nothing to return. Most interview framings also assume adjacent samples are never equal, which makes the peak strict; flat runs are discussed below. ## Sortedness is sufficient, not necessary The usual mental model — "binary search requires sorted input" — states a special case as if it were the rule. What halving really requires is a **decision procedure at the probe point that provably preserves an answer in the half you keep**. In classic search-for-a-value, sortedness is what supplies that procedure: if the target is greater than the midpoint value, every element to the left is also smaller than the target, so the left side cannot hold it. Sortedness is one way to buy the guarantee. It is not the only way. Peak finding buys the same guarantee from a completely different fact: an unsorted series is still a sequence of rises and falls, and a rise cannot continue forever inside a finite array. ## The halving argument Probe the midpoint and compare it with its right neighbour. - If `a[mid] < a[mid+1]`, the readings are rising at `mid`. Walk right from `mid+1`. Either the values keep rising until the last index — which is then a peak under the end convention — or at some point they stop rising, and the last index before that drop is a peak. Either way the sub-range strictly to the right of `mid` contains at least one local maximum, so the left half can be discarded. - If `a[mid] >= a[mid+1]`, the same argument runs leftward: walk left from `mid` and you either keep rising to index `0`, which is then a peak, or you turn over at one. So the range from the low bound through `mid` contains a peak, and the right half can go. Notice what the argument does **not** claim: it never says the discarded half is peak-free. It usually is not. The claim is only that the surviving half still contains one, which is all a search for *any* peak needs. ## Cost Each step does O(1) comparisons and halves the range, so the recurrence is T(n) = T(n/2) + O(1), giving O(log n) time. Written iteratively it uses O(1) auxiliary space; written recursively the call stack is O(log n), and recursion depth counts as space. Contrast this with the obvious alternative — scan every sample and keep the largest — which is O(n) but answers a strictly stronger question. ## What you are promised, and what you are not The result is a valid local maximum. It is **not**: - the global maximum — a taller peak elsewhere is entirely possible and no comparison ever ruled it out; - deterministic across implementations — a variant that probes `a[mid]` against its *left* neighbour, or rounds the midpoint the other way, will often return a different index on the same input, and both are correct; - an enumeration — you get one peak, never the list of them. Listing all local maxima requires touching every element, so it is inherently O(n). Any requirement phrased as "the highest reading" or "all the turning points" is therefore the wrong fit for this technique, and reaching for it anyway is the single most common misuse. ## Boundaries and flat runs Two details cause almost every bug. First, the probe touches `mid+1`, so the loop bounds must guarantee that index exists; a loop condition of `lo < hi` with a floored midpoint does, because it forces `mid < hi`. Second, equal adjacent values break the reasoning's grip: if `a[mid] == a[mid+1]` the local probe carries no information about which side holds a *strict* peak, so either you accept the "greater than or equal to both neighbours" definition — under which the halving loop still returns a valid answer — or you may be forced into a linear scan. ## When a linear scan wins anyway For a few hundred samples the constant factors and the extra reviewer-minutes make the O(n) scan the better engineering choice, and it answers more questions (global maximum, peak count, all peaks) for the same one pass. The logarithmic method earns its keep when the series is large, random access is cheap, and "any turning point" is genuinely the question being asked — or when probing a sample is itself expensive, since it makes O(log n) probes instead of n.