Binary Search on the Answer
Scenario
A physics engine calculates that a high-velocity bullet is in front of a wall at Frame 1, and completely behind the wall at Frame 2. It missed the collision entirely ('tunneling').
How does the engine calculate the exact fractional millisecond the collision occurred without doing infinite math?
Why it exists
Problem: Many optimization problems (e.g., 'minimize the maximum load', 'maximize the minimum distance') are mathematically complex to solve directly. There is no physical array to search.
Naive approach: Guess every possible answer starting from 0, run a simulation to see if the guess works, and stop at the best one. This linear scan of the theoretical answer space takes too long.
Better idea: If the problem space is monotonic (if a guess works, all larger guesses also work; or vice versa), we can Binary Search the theoretical answer range itself. We guess the midpoint, run a validation function, and halve the search space based on the result.
Mental model
You are guessing a number between 1 and 100. I only tell you 'Too High' or 'Too Low'. You don't need a physical list of numbers; you just guess 50, then 25 or 75, honing in on the concept of the answer.
Abandon the physical array. Define a `low` and `high` representing the theoretical minimum and maximum possible answers. Calculate `mid`. Pass `mid` into a separate `isValid(mid)` subroutine that simulates the problem constraints. Based on whether the simulation succeeds or fails, adjust `low` or `high`.
Repeated decision: Does `isValid(mid)` return true? If yes, record it as a potential answer and try to optimize further (e.g., search the left half for a smaller valid answer). If no, search the right half.
Explanation
Binary Search on the Answer (often called Bisection) requires a strict property: Monotonicity. This means the answers form a boolean progression like `[False, False, True, True, True]`. Once a threshold is crossed, the validity never flips back.
The algorithm is split into two parts: the O(log(Range)) binary search, and the O(N) `isValid()` function. Total time is O(N log(Range)).
When applying this to continuous decimal variables (floating-point bisection), using `low <= high` causes an infinite loop due to floating-point precision exhaustion. The hardware cannot represent the microscopic fraction separating the pointers. Instead, you must use a tolerance threshold (epsilon): `while (high - low > 1e-7)`. This guarantees termination while providing massive precision.
In engineering, Continuous Collision Detection (CCD) in physics engines uses bisection over time to find the exact fractional millisecond of impact. Networking protocols use bisection (Path MTU Discovery) to find the maximum packet size a network route can handle without fragmentation.
Key points
- No Physical Array: The search space is the mathematical range of possible answers, not array indices.
- Monotonicity Required: The `isValid()` function must produce a clean `False -> True` or `True -> False` boundary.
- Floating-Point Epsilon: Use `while (high - low > 1e-7)` for decimal bisection to prevent infinite loops.
Pattern: Bisection / Min-Max Optimization
Recognition cues:
- The problem asks to 'minimize the maximum' or 'maximize the minimum'.
- Direct mathematical formulas are too complex, but verifying a 'guessed' answer is easy.
- The phrasing implies a threshold: 'What is the smallest capacity that can ship all packages?'
Failure signals
- You used `while (low <= high)` on floating-point numbers and got a Time Limit Exceeded due to precision exhaustion.
- Your `isValid()` function is O(N^2), making the total algorithm O(N^2 log(Range)) which is too slow.
Engineering examples
Physics Engines (Continuous Collision Detection)
Preventing high-speed objects from tunneling through walls between discrete frames.
Bisection searches the time interval [0.0, 1.0] between frames. If they overlap at t=0.5, the collision was earlier (search left). It zeroes in on the exact impact millisecond.
Path MTU Discovery (Networking)
Finding the largest packet size a route can handle without dropping it.
Sends probe packets of varying sizes. A dropped packet means 'too big' (search smaller). A successful packet means 'can go bigger' (search larger).
When not to use
- The problem is not monotonic: If the `isValid()` results look like `[True, False, True, False]`, you cannot use bisection because you don't know which half of the space to discard.
Common mistakes
- Writing a slow validation function: The `isValid()` function runs on every step of the binary search. If `isValid()` is not efficient (e.g., O(N^2) instead of O(N)), the entire algorithm will fail performance tests.
- Incorrect initialization of bounds: Setting `high` too low will exclude the correct answer. Always ensure `high` represents the absolute worst-case mathematical maximum possible answer.
Glossary
- Monotonicity
- A property where values only ever go up or only ever go down.
- floating-point bisection
- A method of cutting a range of decimal numbers in half repeatedly to find an answer.
- Continuous Collision Detection
- A physics simulation technique to precisely find when objects hit each other.
Recall questions
- What does 'monotonicity' mean in the context of Binary Search on the Answer?
- Why must you use an epsilon (e.g., `1e-7`) for the loop condition when doing bisection on floating-point numbers?
- What is the time complexity of Binary Search on the Answer?
Questions & answers
A conveyor belt has packages of various weights. You have D days to ship all packages in order. Find the minimum weight capacity the ship must have to achieve this.
Binary search the capacity. `low` is the max single package weight. `high` is the sum of all weights. `isValid(capacity)` simulates shipping greedily. If you need <= D days, the capacity works, try a smaller one. Otherwise, try a larger one.
Approach: Minimize the Maximum (Bisection).
Koko loves to eat bananas. There are N piles of bananas. She has H hours. Find the minimum bananas-per-hour eating speed K she needs to finish all piles.
Binary search the speed K. `low = 1`. `high = max(piles)`. `isValid(K)` calculates total hours needed by summing `ceil(pile / K)`. If hours <= H, it's valid (try smaller K). Else, try larger K.
Approach: Binary Search on the Answer.
Interesting facts
- Machine Learning engineers use this exact technique (often formalized as the Bisection Method) to find optimal threshold cutoffs for classification models without training the model infinitely.
Continue learning
Previous: Binary Search
Previous: Lower Bound
Related: Binary Search
Related: Lower Bound