Searching & Binary Search

A plain binary search returns the moment a midpoint matches, so which member of a run of equal keys comes back depends only on where the splits fell. The leftmost occurrence requires searching on after a hit.

Each comparison discards half of the remaining candidates, so the range shrinks n, n/2, n/4, down to one. The number of halvings needed to reach a single candidate is log2(n), so that many comparisons suffice.

Adding lo and hi can overflow a fixed-width signed integer once indices grow large, wrapping negative and yielding an out-of-range midpoint. Computing lo + (hi - lo) / 2 keeps every intermediate value inside the valid index range.

Linear search is O(n) because the bound is set by the worst case: a match in the last position, or no match at all, forces a scan of every element. Early exit improves lucky runs, not the growth rate.

Nothing signals an error. The file is ordered by id but the search compares amounts, so each halving step discards the wrong half and returns an arbitrary index or a false "not present" — silent garbage, not an exception.

"Sorted matrix" means one of two things: fully sorted row-major, where the grid reads as one non-decreasing sequence and binary search costs O(log mn); or merely row- and column-sorted, which has no global order and needs corner elimination at O(m+n).

Binary search needs a rule that safely discards half the input, not sorted data. Comparing a sample with its right neighbour shows an uphill direction, and the uphill half always still contains a local maximum, so halving stays correct.

Standard binary search assumes a total ascending order, so one comparison against the midpoint tells it which side to discard. Rotation breaks that assumption, so the discard rule can throw away the very half that holds the target.

Binary search on the answer costs O(check) x O(log R), where R is the span of candidate answer VALUES. The log factor comes from the value range, not the input size, and the feasibility check usually dominates.

Sweep the batches in order, adding each to the current worker while its running load stays within the limit and opening a new worker otherwise, then report whether the worker count is at most k.

Binary search needs only a monotone yes/no test over an ordered range of candidates, not a stored array. If feasible(x) is false below a threshold and true above it, halve that virtual boolean sequence to find the first true.

Lower bound returns the first index whose element is at least the target: the first copy. Upper bound returns the first strictly greater index: one past the last copy. Their difference is the occurrence count.

A match proves the target exists there, but a smaller matching index can only lie strictly left. So the loop saves the hit as its best candidate, discards the midpoint and everything right of it, and continues.

About 30 probes for a billion entries and about 40 for a trillion: the worst case is floor(log2 n) + 1. Multiplying the data by a thousand adds only ten probes, because log2(1000) is roughly 10.

Rounding down makes the midpoint equal the lower bound whenever two candidates remain, so assigning it back to the lower bound leaves the range unchanged and the loop repeats that state forever. Every branch must strictly shrink the range.

Sorting costs O(n log n) before the O(log n) lookup, so the total is dominated by the sort and is strictly worse than one O(n) scan. Ordering only pays once its cost is amortized over enough later queries.

The top-right cell is the largest in its row and smallest in its column, so one comparison rules out a whole line: too big drops the column, too small drops the row. That bounds the walk at m + n steps.

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.

Compare the midpoint value against a range endpoint, never against the target. If the midpoint value is at most the value at the high end, the segment from midpoint to high is in order; otherwise the low-to-midpoint segment is.

Prove it by argument, not by sampling: show that any solution meeting the constraint at one candidate still meets it when the candidate moves in the relaxing direction. Sampling can disprove monotonicity with a single counterexample, but never establish it.

Binary search on the answer searches the range of possible answers, because the input is not ordered by the quantity you want. Each midpoint is a candidate answer, tested by a feasibility check that returns only yes or no.

It probes index 1, then 2, 4, 8 and so on until a probe reaches or passes the target or falls off the end, then binary searches only the interval between the previous probe and that one.

Interpolation search guesses the probe index by linearly interpolating the sought key between the two endpoint values, instead of always taking the midpoint. It needs sorted, randomly accessible keys you can do arithmetic on, and it only pays off when values are spaced near-uniformly.

Binary search needs a monotone test, and one probe on a fall-then-rise curve cannot say which side the minimum is on. Ternary search compares two interior probes to discard the outer third that provably cannot contain it.

A midpoint that tests feasible is itself a candidate answer. The loop's invariant is that the smallest feasible value lies inside lo..hi, so a true probe narrows hi to mid; mid - 1 would discard the proven value.

Because mid may itself be the answer. A midpoint that satisfies the predicate is the earliest qualifying index found so far, so it must stay in range; mid - 1 discards it and the search returns a position too far left.

A floored midpoint equals the low bound whenever two elements remain, so the branch that keeps the midpoint by assigning it back to the low bound makes no progress and the iteration repeats identically. Rounding the midpoint up fixes it.

The halving argument counts comparisons but assumes reaching the midpoint is cheap. In a linked structure you must walk to the midpoint, and the walks sum to n/2 + n/4 + ... which is O(n), so total work is linear.

Four things move together: the initial upper bound (one past the end versus the last index), the loop condition, which shrink step keeps the midpoint, and how an empty range is spelled. Never mix halves of the two conventions.