Searching & Binary Search

Both phases are bounded by where the answer sits, not by how much data exists: doubling stops at the first power of two past position i, and the binary search then covers an interval no wider than i.

Because reads past the last entry answer the search predicate as satisfied, the predicate stays false-then-true across the whole bracket, so a first-true binary search converges even when the upper index lies beyond the data.

On near-uniformly spaced keys each interpolated probe narrows the remaining range from about n to about the square root of n, which compounds to O(log log n) expected probes. When spacing is skewed, the probe creeps toward one end an element at a time, giving O(n).

The alternative is impossible: if the minimum sat at or left of m1, the curve would rise from m1 to m2, forcing f(m1) below f(m2) — the opposite of what was measured. So the minimum lies strictly right of m1.

A zero-valued record conflates three different outcomes: the entry is missing, the collection was empty, and the entry exists but its value happens to be zero or disabled. Callers cannot tell them apart, so a failed load silently reads as 'everything off'.

Binary search requires a monotone predicate over the search range: false everywhere below some boundary and true everywhere above it. A sorted collection is just the case where "is this element at least the target" happens to be monotone.

Reading order packs cols entries into every row, so flat position mid sits at row mid / cols, column mid % cols. Dividing by the row count instead coincides only on square grids, which is why that bug survives square tests.

Bitonic search runs in two stages: a slope-comparison binary search locates the single apex, then two ordinary binary searches cover the rising side ascending and the falling side descending. Three logarithmic passes in sequence are still O(log n).

The midpoint itself may be the wrap point: when its value is not greater than the value at the high end, it stays a candidate for the smallest element, so discarding it can lose the answer.

Take the upper bound of the score; n minus that index counts the players who strictly beat it, so the rank is one more. That index is also the insertion position, but the insert costs O(n) moves.

Walking outward from a match touches one element per duplicate, so counting costs O(log n + k) for a run of k equal keys, and k grows with the very skew that motivated the query. Two boundary searches stay O(log n).

Rarely on stack-depth grounds: recursion nests only floor(log2 n) + 1 deep, about 30 frames at a billion entries. Insist on the loop when the stack is genuinely tiny or already deep, or when per-call overhead matters in a hot path.

The invariant is that if the sought value is present, its position lies inside the current range. Check that the initial bounds establish it, that each branch discards only ruled-out positions, and that an empty range at exit proves absence.

Push back: the O(log log n) figure is an expectation conditional on near-uniform spacing, and transaction amounts are heavy-tailed, so probes creep from one end and the search degrades toward O(n). Adopt it only where spacing is guaranteed by construction, not hoped for.

A plateau breaks the elimination argument. Equal probe values pin the optimum between them only under strict unimodality; on a flat run it is uninformative: the plateau can extend past both probes, so the discarded third may hold the optimum.

At sixty-four elements the asymptotics barely apply: a scan of fixed-size contiguous records is a tight, predictable loop over cheap comparisons, while a tree pays pointer chasing, per-node overhead, and build and maintenance cost that so few elements never repay.

No. The precondition is all-or-nothing: one inversion can send a probe down the half that does not contain the target, and the search returns a wrong answer with no error. Restore or enforce the ordering first, or scan.

Per-row binary search costs O(m log n) and beats the O(m+n) corner walk only on short, wide grids — few rows, many columns — because the row count multiplies the logarithm. On tall or square grids the walk wins outright.

Duplicates can make the midpoint tie with both endpoints, leaving the ordered side unidentifiable. The only safe move is then to shrink one bound by a single position, so the worst case rises from O(log n) to O(n).

The probe formula divides by a[hi] - a[lo], so equal endpoint values make the denominator zero and the probe computation fault or produce nonsense. It happens on any plateau of duplicates and, in the textbook loop, on every single-element range too.

Writing the target into a spare slot just past the last live record guarantees the loop terminates on a match, so each iteration tests equality only, never the end of the buffer. It costs a writable spare slot, a restore, and a check that the hit was not the sentinel.

Binary search the range of possible sum values rather than the pairs. With both lists sorted, count in one linear sweep how many pairs sum to at most a candidate x, then take the smallest x whose count reaches k.

Galloping wins when the size is unavailable, expensive or stale, or when targets cluster near the head, since its cost tracks the answer's position. A cheap, exact size wins for uniformly placed targets: one plain search halves the probes.

Ternary search keeps two-thirds of the interval per step and spends two probes doing it — about 3.4 evaluations per halving. Bisecting on the slope's sign halves the interval for one or two. Same complexity class, worse constant.

Usually not in its textbook form: eleven serial twenty-minute probes cost most of a day, and one noisy probe near the flip point permanently discards the correct half. Probe in parallel batches and ship with margin.

Promise a local peak only when consumers genuinely need a point where the climb stops and the input is guaranteed single-humped, so the two answers coincide. Promise the global maximum whenever results are compared, alerted on or reported.

A rotation-aware search is not worth shipping when the range is small, queried rarely, or written by code you control. Recording the wrap position at write time, or normalising once on read, removes the rotation and a class of boundary bugs.