12. Parametric Search

What you'll learn

• 1Convert an optimization problem to a feasibility check
• 2Binary search on the answer space
• 3Solve classic 'router placement' problems

Overview

Many problems ask 'what's the largest X such that we can still satisfy a constraint?'. The constraint check itself runs in linear time. Binary-searching on X gives an O(n log V) solution where V is the answer range — often the only way to fit within the time limit.

Core Concepts

1. The pattern

Most parametric problems have monotonic feasibility: if X works, X-1 also works (or vice versa). That monotonicity is what enables binary search.

def parametric_search(lo, hi, check):
    """Find max X in [lo, hi] such that check(X) is True.
       Assumes if check(X) is True, check(X-1) is too."""
    while lo < hi:
        mid = (lo + hi + 1) // 2     # bias up to avoid infinite loop
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

2. Canonical example: router placement

Given N houses on a line and C routers, place the routers so the *minimum* distance between any two is *maximized*.

def can_place(houses, c, gap):
    placed = 1
    last = houses[0]
    for h in houses[1:]:
        if h - last >= gap:
            placed += 1
            last = h
    return placed >= c

def solve(houses, c):
    houses.sort()
    lo, hi = 1, houses[-1] - houses[0]
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if can_place(houses, c, mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

3. When to use parametric search

• Problem asks for max or min of something measurable.
• You can write a check(X) that returns True/False in O(n).
• Feasibility is monotonic in X.
• Range of X is large (so iterating linearly would TLE).

Examples

Example 1 — src/01_router.py

Router placement — the classic BOJ 2110.

Example 2 — src/02_wood_cutting.py

Wood cutting — find the max blade height to harvest M meters of wood.

Example 3 — src/03_ranking_min_max.py

Schedule jobs on machines to minimize the maximum load.

Example 4 — src/04_sqrt_decimal.py

Binary search on real numbers (square root to N decimal places) — change the termination condition.

Common Mistakes

1. Using (lo + hi) // 2 with `lo = mid` → infinite loop. Use (lo + hi + 1) // 2 when searching for max.
2. Forgetting that feasibility must be monotonic. Test small inputs by hand.
3. Binary search range too small — set hi to the largest plausibly correct answer.
4. Floating-point binary search without termination condition — use `for _ in range(100)` instead of equality.

Recap

• Optimization → feasibility + binary search.
• Check function in O(n), search in O(log V).
• Watch the (lo + hi + 1) // 2 trick for upper-biased search.

Try It

1. BOJ 2110 (Router placement).
2. BOJ 2805 (Wood cutting).
3. BOJ 1654 (LAN cables).