7.25 Parametric Search
Parametric search is a technique for solving optimization problems by repeatedly answering decision questions.
7.25 Parametric Search
Parametric search is a technique for solving optimization problems by repeatedly answering decision questions.
It is closely related to binary search on answer. The distinction is mostly one of emphasis. Binary search on answer describes the implementation pattern. Parametric search describes the modeling step: turn an optimization problem over a parameter into a sequence of feasibility tests.
Instead of directly computing the best value, you ask whether a candidate parameter is good enough. If the answer is monotone, binary search can locate the optimal threshold.
This technique is useful in scheduling, load balancing, packing, geometry, network design, manufacturing, and resource allocation.
Problem
Suppose you have several jobs:
[7, 2, 5, 10, 8]
You have:
2 workers
Jobs must be assigned in order. Each worker receives a contiguous block of jobs.
You want to minimize the maximum workload assigned to any worker.
One possible assignment:
Worker 1: [7, 2, 5] = 14
Worker 2: [10, 8] = 18
Maximum workload:
18
Another assignment:
Worker 1: [7, 2, 5, 10] = 24
Worker 2: [8] = 8
Maximum workload:
24
The optimal answer is:
18
A brute-force search over all partitions is expensive.
Solution
Convert the optimization problem into a decision problem.
Instead of asking:
What is the smallest possible maximum workload?
ask:
Can all jobs be assigned so that no worker receives more than X work?
For X = 15:
Worker 1: [7, 2, 5] = 14
Worker 2: [10] = 10
Worker 3: [8] = 8
Requires three workers.
Result:
false
For X = 18:
Worker 1: [7, 2, 5] = 14
Worker 2: [10, 8] = 18
Requires two workers.
Result:
true
The feasibility pattern is monotone:
X too small -> false
X large enough -> true
Binary search finds the first feasible X.
Feasibility Function
The feasibility function greedily packs jobs into the current worker until adding another job would exceed the limit.
func CanAssign(
jobs []int,
workers int,
limit int,
) bool {
used := 1
current := 0
for _, job := range jobs {
if job > limit {
return false
}
if current+job <= limit {
current += job
} else {
used++
current = job
}
}
return used <= workers
}
This function answers the decision question:
Is limit sufficient?
It does not compute the optimum directly.
It only verifies a candidate.
Binary Search Over the Parameter
The smallest possible answer is the largest single job.
The largest possible answer is the sum of all jobs.
func MinMaxWorkload(
jobs []int,
workers int,
) int {
lo := 0
hi := 0
for _, job := range jobs {
if job > lo {
lo = job
}
hi += job
}
for lo < hi {
mid := lo + (hi-lo)/2
if CanAssign(jobs, workers, mid) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
Example:
jobs := []int{7, 2, 5, 10, 8}
fmt.Println(MinMaxWorkload(jobs, 2))
Output:
18
Understanding the Parameter
The parameter is:
maximum allowed workload
Binary search does not care that the parameter represents workload. It only needs an ordered domain and a monotone predicate.
For small values:
false
For large values:
true
The optimal answer is the boundary.
This pattern appears across many domains.
Choosing Bounds
Good bounds simplify both correctness and performance.
For the workload problem:
lo = max(jobs)
because no worker can receive less capacity than the largest single job.
hi = sum(jobs)
because one worker can do all jobs.
The true answer must lie inside:
[lo, hi]
Poor bounds can cause incorrect results or unnecessary iterations.
Example: Minimum Days
Suppose machines produce items at different rates.
machines = [2, 3, 7]
A machine with rate 2 produces one item every two days.
You need:
10 items
Question:
What is the minimum number of days?
Decision version:
Can the machines produce at least 10 items in D days?
Feasibility:
func CanProduce(
rates []int,
goal int,
days int,
) bool {
total := 0
for _, rate := range rates {
total += days / rate
if total >= goal {
return true
}
}
return false
}
If production is possible in D days, it is also possible in any larger number of days.
The predicate is monotone.
Example: Aggressive Placement
Suppose positions are:
[1, 2, 4, 8, 9]
Place:
3 routers
Maximize the minimum distance between routers.
Decision version:
Can we place 3 routers with distance at least D?
Feasibility:
func CanPlace(
positions []int,
count int,
distance int,
) bool {
placed := 1
last := positions[0]
for _, pos := range positions[1:] {
if pos-last >= distance {
placed++
last = pos
if placed >= count {
return true
}
}
}
return false
}
Here the monotonicity is reversed.
If distance D is feasible, smaller distances are also feasible.
The truth pattern looks like:
true true true false false
To maximize a feasible value, search for the last true rather than the first true.
Last True Template
For maximum feasible values, use a last-true search.
func LastTrue(
lo int,
hi int,
ok func(int) bool,
) int {
for lo < hi {
mid := lo + (hi-lo+1)/2
if ok(mid) {
lo = mid
} else {
hi = mid - 1
}
}
return lo
}
The +1 in the midpoint calculation biases upward and prevents infinite loops when lo and hi are adjacent.
Usage:
answer := LastTrue(
0,
positions[len(positions)-1]-positions[0],
func(d int) bool {
return CanPlace(positions, count, d)
},
)
First True Versus Last True
Many mistakes come from using the wrong boundary direction.
| Goal | Predicate Shape | Template |
|---|---|---|
| Minimize feasible value | false...true | First true |
| Maximize feasible value | true...false | Last true |
| Find first invalid value | true...false | First false |
| Find last valid value | true...false | Last true |
Always determine the truth pattern before writing code.
The algorithm follows the boundary, not the problem statement.
Parametric Search in Geometry
Consider finding the smallest radius that covers all points.
Decision version:
Can radius R cover every point?
If a radius works, every larger radius works.
Truth pattern:
false false true true
Search for the first true value.
For real-valued parameters, use floating-point binary search with an error tolerance.
Parametric Search in Networks
Suppose a network must support a traffic demand.
Question:
What is the minimum bandwidth needed?
Decision version:
Can bandwidth B route all required traffic?
If B works, any larger bandwidth also works.
The problem becomes a boundary search over bandwidth.
The feasibility check may involve graph traversal, flow computation, or simulation. Binary search only controls the outer parameter.
Parametric Search in Scheduling
Many scheduling problems fit this model.
Examples:
Minimum number of machines
Minimum shift length
Minimum processing speed
Maximum acceptable delay
Minimum buffer size
Each candidate parameter is tested by a scheduling feasibility routine.
If feasibility is monotone, binary search applies.
Correctness Argument
A parametric-search solution usually needs three claims.
First, the optimal answer lies within the chosen bounds.
Second, the feasibility function is correct for a fixed candidate.
Third, the feasibility function is monotone over the search domain.
Once those are established, binary search correctness follows from the boundary invariant.
For first true:
All values before the boundary are infeasible.
All values at or after the boundary are feasible.
For last true:
All values up to the boundary are feasible.
All values after the boundary are infeasible.
Complexity Analysis
Let:
R = size of search range
T = cost of feasibility test
Integer parametric search costs:
O(T log R)
Floating-point parametric search costs:
O(T log((hi - lo) / epsilon))
The feasibility function usually dominates total runtime.
Improving T often matters more than improving the binary search implementation.
Common Mistakes
A common mistake is failing to prove monotonicity. Without monotonicity, binary search is invalid.
Another mistake is using a first-true template for a last-true problem, or the reverse.
A third mistake is choosing bounds that exclude the true optimum.
A fourth mistake is making the feasibility function too expensive. If each check costs O(n²), the outer binary search may still be too slow.
Finally, beware of overflow when computing sums, midpoints, or production counts.
Takeaway
Parametric search turns optimization into repeated feasibility testing. By identifying an ordered parameter and proving that feasibility changes monotonically, many hard-looking minimization and maximization problems reduce to boundary search. The implementation is usually simple; the modeling is the real work. Choose valid bounds, write a correct feasibility function, determine whether you need first true or last true, and then let binary search locate the optimal parameter.