Monotonic Predicate Framing

## The requirement is a predicate, not a container Binary search is usually first met as "find a value in a sorted array", and the array then gets remembered as the requirement. It is not. Binary search needs three things: a domain of candidates with a total order, the ability to jump directly to any candidate in that domain, and a boolean test over candidates whose answer changes at most once as you walk the domain upwards. A sorted array satisfies all three — the test is "is this element at or past the value I am looking for?" — but it is one instance of the pattern, not the pattern itself. ## The virtual boolean sequence Write the test as `feasible(x)`, defined for every candidate `x` in `lo..hi`. If it is monotone in the sense above, reading the whole range would give: ``` x: lo ... ... hi feasible: F F F F T T T T ``` The smallest candidate that works is the position of the first `T`. In every way that matters to the search this is a sorted array of booleans — except it is never built. Each entry is produced on demand by running the check, and a search over a range of width `W` produces only about `log2(W)` of them. A range of a billion candidates costs roughly thirty checks. That is exactly why the technique reaches answer spaces that could never be enumerated, and why "there is no array here" is not an objection. ## Turning an optimisation into a predicate The reframe is mechanical once you have seen it: 1. Identify the single ordered scalar being minimised or maximised. If two quantities are being traded off at once, this technique does not apply directly. 2. Freeze it. Instead of asking "what is the best value?", pick a candidate value and ask a yes/no question: "with this value, can the requirement be met?" 3. Argue monotonicity — that the yes/no answer flips at most once over the range, in a known direction. 4. Bracket the answer with `lo` and `hi`. 5. Search for the first true (minimisation) or the last true (maximisation). ### A worked reframe A glass line anneals panes by holding them in a cooling furnace; cool them too fast and some panes crack. You want the shortest cooling duration, in whole minutes, under which the whole day's batch survives, and you have a test rig that can run a batch at any chosen duration and report cracks. Directly computing the minimum needs a thermal-stress model. The predicate does not: `feasible(D)` = "no pane in the batch cracks when cooled for D minutes". Monotonicity is arguable from the physics direction alone — more cooling only relaxes the constraint, so a batch that survives `D` survives `D + 1` for the same reason. Bounds: `lo = 1`, `hi = 1440` (a full day, comfortably feasible). About eleven checks replace 1440. Notice what the reframe bought. The optimisation question needed a model; the feasibility question needed only a test you already had. That trade — replacing "compute the answer" with "check an answer" — is the whole idea. ## First true and last true Minimisation gives `F…F T…T` and you want the first true. Maximisation gives the mirror image, `T…T F…F`, and you want the last true. They are the same search with the boundary conventions flipped; mixing the two shapes up is the most common implementation bug in the technique. ## Where the bounds come from `hi` should be a candidate you can argue is feasible (or a bound you can argue the answer cannot exceed); `lo` should be one you can argue is infeasible, or simply the smallest legal value in the domain. The two possible mistakes are badly asymmetric. Bounds that are far too wide cost only extra halvings — widening a range a thousandfold adds about ten checks — while an upper bound set below the true answer puts the answer outside the searched window entirely, and the loop returns the top of the range as though it had worked, with no error and no signal. Err wide. ## Where the technique does not apply - Feasibility flips more than once across the range: the search will still terminate and still return a number, and that number can be wrong. - The thing being optimised is not a single ordered scalar. - The check cannot be run at a candidate independently of knowing the answer — a circular predicate is no predicate. - The domain is continuous: still fine, but there is no discrete step to land on, so termination has to be decided by an iteration count or a tolerance rather than by `lo == hi`. ## The wrong answer this displaces "Binary search needs a sorted array" is the misconception the whole technique exists to break. The candidates need not be indices and need not be stored: they are capacities, durations, thresholds, counts, radii, budgets or real numbers. When a sorted array is present, it is merely a convenient way to evaluate the predicate.