Pattern Guide
Binary Search on Answer
"When you can check "is X achievable?" in O(f(n)), find optimal X in O(f(n) log range)."
Binary search on the answer (parametric search) solves optimization problems by converting them to decision problems: "Is it possible to achieve value ≤ X?" If this check is monotone (feasible for all X ≥ threshold), binary search finds the threshold. Covers: minimize maximum, maximize minimum, k-th element in matrix, allocation problems, and any problem where the answer has a monotone feasibility function.
Problems you can solve with this pattern
5 problems · click any to start solving
// Template: find minimum X such that check(X) is true
// Requires: if check(X) is true, then check(X+1) is also true
function binarySearchAnswer(lo, hi, check) {
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (check(mid)) hi = mid; // X is feasible, try smaller
else lo = mid + 1; // X is not feasible, need larger
}
return lo; // smallest feasible X
}
// Template for maximum (largest X where check is true):
function binarySearchAnswerMax(lo, hi, check) {
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2); // upper mid to avoid infinite loop
if (check(mid)) lo = mid; // feasible, try larger
else hi = mid - 1; // not feasible, go smaller
}
return lo; // largest feasible X
}
// Floating point binary search (e.g., "find x where f(x) = target"):
function binarySearchFloat(lo, hi, check, eps = 1e-9) {
for (let i = 0; i < 100; i++) {
const mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid;
}
return (lo + hi) / 2;
}The pattern: (1) Identify that the answer has a monotone structure — if X is achievable, so is X+1 (or X-1). (2) Write a check(X) function: "can we achieve value ≤ X?" (3) Binary search for the smallest X where check(X) is true. Key: the check function must be O(n) or O(n log n), making total complexity O(n log(range)). Works for: minimize, maximize, k-th smallest, feasibility with thresholds.
// Template: find minimum X such that check(X) is true
// Requires: if check(X) is true, then check(X+1) is also true
function binarySearchAnswer(lo, hi, check) {
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (check(mid)) hi = mid; // X is feasible, try smaller
else lo = mid + 1; // X is not feasible, need larger
}
return lo; // smallest feasible X
}
// Template for maximum (largest X where check is true):
function binarySearchAnswerMax(lo, hi, check) {
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2); // upper mid to avoid infinite loop
if (check(mid)) lo = mid; // feasible, try larger
else hi = mid - 1; // not feasible, go smaller
}
return lo; // largest feasible X
}
// Floating point binary search (e.g., "find x where f(x) = target"):
function binarySearchFloat(lo, hi, check, eps = 1e-9) {
for (let i = 0; i < 100; i++) {
const mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid;
}
return (lo + hi) / 2;
}Check function design:
- For "minimize max": check(X) = "can we stay ≤ X?" → greedy
- For "maximize min": check(X) = "can we achieve ≥ X everywhere?" → greedy
- For "k-th element": check(X) = "how many elements ≤ X?" → count then compare to k
Boundary handling:
- Minimize: lo=min feasible, hi=max possible; if check(mid) → hi=mid else lo=mid+1
- Maximize: use upper mid (lo+hi+1)>>1; if check(mid) → lo=mid else hi=mid-1
- Floating point: 100 iterations of (lo+hi)/2 gives ~30 decimal digits of precision