Searching on the Answer (Binary Search on Answer)

Binary search on the answer guesses a candidate value (minimum time, maximum capacity) and checks feasibility in poly time. If feasible is monotone in the guess, you can binary search the answer space.

Why this shows up in the real world

Factory scheduling asks smallest number of lines that can meet throughput—feasibility is a greedy check per guess. Network QoS binary-searches delay budgets.

Core idea (explained for students)

Define feasible(x) -> bool. Find smallest x with feasible(x) true: search lo..hi, mid test, shrink half. Classic for minimax and allocation problems.

Try this in Python

def min_k_for_sum_at_least(target: int, max_chunk: int) -> int:
    lo, hi = 1, target
    while lo < hi:
        mid = (lo + hi) // 2
        if mid * max_chunk >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo


print(min_k_for_sum_at_least(100, 30))

Common mistakes

• Wrong initial hi so the true answer lies outside the bracket.
• Feasibility check itself is too slow—dominates total runtime.

Key takeaways

• Prove monotonicity of feasibility before coding the search.
• Reuse one feasibility routine for both check and construction.