Optimization -> Decision: The Binary Search Reduction

Quick Revisit
REACH FOR THIS WHEN: you need to optimize a value and the decision version ("can we achieve X?") is easier
KEY DECISION: is the feasibility function monotonic in the answer?
QUICK RULE: "minimize the maximum" or "maximize the minimum" -- reach for binary search on the answer first
SEE ALSO: Graph Modeling, DP State Design

Every "find the best X" problem might be a "can we achieve X?" problem in disguise.
Prerequisites: Binary Search

The Fundamental Idea

You want to minimize some value. That's hard -- you'd need to explore all possibilities and prove one is best.

But what if someone gave you a candidate answer and asked: "is this achievable?" That's often a completely different (easier) problem. And if you can answer that yes/no question efficiently, binary search finds the optimum.

The template:

lo, hi = bounds on the answer
while lo < hi:
    mid = (lo + hi) / 2
    if feasible(mid):
        hi = mid       // mid works, try smaller
    else:
        lo = mid + 1   // mid doesn't work, need bigger
return lo

The insight: you're converting an optimization problem into a decision problem, then solving the decision problem $O (\log (range))$ times.

Read this twice: binary search is not the solution. The feasibility check is the solution, repeated logarithmically. If your feasible(mid) is hand-wavy or wrong, no amount of binary-search scaffolding will save you. Most "I implemented binary search and it gave the wrong answer" bugs are decision-version bugs.

Five Reductions in the Wild

1. "Minimum time, splitting an ordered sequence" -> "Can we finish in time T?"

Setup. Given $n$ jobs with durations in a fixed order, partition them into $k$ contiguous groups (workers receive consecutive jobs). Minimize the maximum group sum (the makespan).

Decision version. Given time budget $T$ : walk left to right, summing into the current worker. When adding the next job would exceed $T$ , start a new worker. Did you use $\leq k$ workers?

Binary search on $T$ between $max (a_{i})$ and $\sum a_{i}$ .

Caveat. This greedy works only because the partition is into contiguous groups in the given order. Arbitrary scheduling on identical workers (any job to any worker) is P||Cmax — NP-hard in general. If the problem allows reordering, this decision check is wrong; for that flavor, see Factory Machines (problem 4 below), where the greedy structure is different.

2. "Maximum minimum distance" -> "Can all distances be >= D?"

Setup. Place $k$ objects among $n$ positions. Maximize the minimum pairwise distance.

Decision version. Given minimum distance $D$ : greedily place objects. Put the first object at position 1. For each subsequent object, pick the leftmost position that's $\geq D$ away from the last placed object. Did you place all $k$ ?

Binary search on $D$ . This is the classic "Aggressive Cows" problem.

cpp

bool canPlace(vector<int>& pos, int k, int minDist) {
    int placed = 1, last = pos[0];
    for (int i = 1; i < pos.size(); i++) {
        if (pos[i] - last >= minDist) {
            placed++;
            last = pos[i];
        }
    }
    return placed >= k;
}

3. "Minimum number of groups" -> "Can we do it with K groups?"

Setup. Partition items into groups subject to constraints (e.g., max sum per group). Minimize groups.

Decision version. Given $K$ groups: try a greedy or DP check to see if $K$ suffices. Binary search on $K$ .

Often the decision version reveals that the answer is monotonic: if $K$ groups work, $K + 1$ definitely work too.

4. "Find the k-th smallest value" -> "How many values are <= X?"

Setup. You have an implicit set of values (e.g., products $a_{i} \cdot b_{j}$ for all pairs). Find the $k$ -th smallest.

Decision version. Given $X$ : count how many values are $\leq X$ . Binary search on $X$ to find the smallest $X$ where the count $\geq k$ .

This is how you solve "k-th smallest element in a sorted matrix" in $O (n \log (range))$ instead of $O (n^{2} \log n)$ .

5. Parallel Binary Search -- Many Queries at Once

Skip on first pass. This is materially harder than the rest of the page; come back after the simpler reductions feel automatic. The full treatment lives in parallel binary search.

Setup. You have $q$ queries, each asking "what's the first time event $e_{i}$ becomes true?" and a sequence of events applied over time.

The reduction. Instead of binary searching independently for each query ( $O (q \cdot \log T \cdot check)$ ), do them all in parallel:

Each query maintains its own [lo, hi] range.
For each round: group queries by their mid value. Simulate events up to each mid, answer all relevant queries, update their ranges.
Repeat for $O (\log T)$ rounds.

Total: $O ((simulation cost) \cdot \log T)$ regardless of $q$ .

When Binary Search Fails

Binary search on the answer requires monotonicity: if the answer $X$ is feasible, then all values "beyond" $X$ (larger or smaller, depending on direction) must also be feasible.

It breaks when:

The feasibility function oscillates: feasible at 5, infeasible at 6, feasible at 7.
The problem has multiple local optima (not unimodal). For unimodal functions, consider ternary search instead.
The decision problem itself is as hard as the optimization. (Binary search only helps when the decision version is easier.)

Recognizing the Pattern

Ask yourself two questions:

"If someone told me the answer was X, could I verify it (or check feasibility) efficiently?" If yes, and the feasibility is monotonic in $X$ , binary search works.
"Is the answer space continuous or integer?" Integer -> standard binary search. Continuous -> run for a fixed number of iterations (e.g., 100) instead of while lo < hi.

cpp

// Continuous binary search (floating point answer)
double lo = 0, hi = 1e18;
for (int iter = 0; iter < 100; iter++) {
    double mid = (lo + hi) / 2;
    if (feasible(mid)) hi = mid;
    else lo = mid;
}
// lo ~= hi ~= answer

Recognition Cues

If you see in the problem...	Binary search on...	Decision version check
"Minimize the maximum"	The maximum value	Can all values be <= X? (greedy)
"Maximize the minimum"	The minimum value	Can all values be >= X? (greedy)
"Minimum time to finish"	Time T	Can we finish in time T? (greedy assign)
"K-th smallest value" (implicit set)	Value X	How many values <= X? (counting)
"Minimum number of groups"	Group count K	Can we do it in K groups? (greedy/DP)
"Maximum length of subarray with property"	Length L	Does a subarray of length L exist? (sliding window)

When NOT to binary search:

Situation	Why it fails	Use instead
Feasibility oscillates (true, false, true)	Monotonicity violated	Linear scan or DP
Multiple local optima	Unimodal but not monotonic	Ternary search
Decision version is as hard as optimization	No simplification gained	Direct optimization

Common Mistakes in Choosing

Assuming monotonicity without checking. Binary search requires: if answer X is feasible, then all values beyond X are also feasible (or all below, depending on direction). Test on small cases.
Off-by-one in bounds. The classic bug: lo = 0, hi = n vs lo = 1, hi = n+1. Get the invariant right: "lo is always feasible" or "hi is always infeasible."
Using binary search when the decision version is equally hard. Binary search only helps when "can we achieve X?" is strictly easier than "find the best X." If both require the same DP, skip the binary search.
Forgetting the continuous case. For floating-point answers, don't use while (lo < hi) -- use a fixed iteration count (e.g., 100 iterations) to avoid infinite loops from floating-point imprecision.
Not tightening bounds. The search range [lo, hi] should be as tight as possible. For "minimum time," lo = max(single job) and hi = sum(all jobs), not lo = 0 and hi = 10^18.

The Power of the Reduction

Why is this reduction so valuable? Because the decision problem often admits a greedy solution, even when the optimization problem doesn't. You trade the complexity of optimization for the simplicity of yes/no checking, repeated logarithmically many times.

It's one of the most reliable tricks in competitive programming: whenever you see "minimize the maximum" or "maximize the minimum," reach for binary search on the answer first.

Cross-References

Binary Search -- the foundational technique
Greedy -- often the decision-version solver
DP vs Greedy Guide -- when the decision check itself is greedy vs DP
Problem Pattern Recognition -- "minimize the maximum" trigger
Graph Modeling -- another reduction approach

Practice Problems

#	Problem	Source	Rating	What You Binary-Search On
1	Aggressive Cows	SPOJ	1500	Minimum distance between cows
2	Splitting Array	CSES	1500	Maximum subarray sum
3	Kth Smallest in Matrix	LeetCode	1600	The value X, count <= X
4	Factory Machines	CSES	1400	Time T
5	Meteors	POI	2200	Parallel binary search

Recap

The core trick: convert "find the best X" into "can we achieve X?" and binary search over X.
Monotonicity is the precondition: feasibility must be monotonic in the answer value.
The decision version is usually greedy: binary search earns you the simplicity of yes/no checking.
"Minimize the maximum" and "maximize the minimum" are the strongest trigger phrases.
Parallel binary search handles many queries at once in O(simulation * log T) total.
Continuous answers: use fixed iteration count (e.g., 100), not while (lo < hi).

Optimization -> Decision: The Binary Search Reduction ​

The Fundamental Idea ​

Five Reductions in the Wild ​

1. "Minimum time, splitting an ordered sequence" -> "Can we finish in time T?" ​

2. "Maximum minimum distance" -> "Can all distances be >= D?" ​

3. "Minimum number of groups" -> "Can we do it with K groups?" ​

4. "Find the k-th smallest value" -> "How many values are <= X?" ​

5. Parallel Binary Search -- Many Queries at Once ​

When Binary Search Fails ​

Recognizing the Pattern ​

Recognition Cues ​

Common Mistakes in Choosing ​

The Power of the Reduction ​

Cross-References ​

Practice Problems ​

Recap ​