Binary Search on the Answer (Parametric Search)
Binary Search on the Answer transforms optimization problems ("minimize the maximum" or "maximize the minimum") into O(log Range) monotonic feasibility checks.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Binary Search on the Answer (Parametric Search)
Whenever a problem asks to "minimize the maximum ..." or "maximize the minimum ...", check if a candidate answer $X$ is monotonic: if $X$ is feasible, every $X' > X$ is also feasible (or vice versa). Then instead of constructing the optimal answer directly, binary search over the answer space [lo, hi] and write a clean $O(n)$ greedy canDo(mid) feasibility checker!
Practice Problems
Intermediate
1. Aggressive Cows / Magnetic Force Between Two Balls (Maximize Minimum Distance, LeetCode 1552)
Place $k$ balls into sorted basket positions pos[] to maximize the minimum distance between any two balls.
Approach: Sort pos. Feasibility canPlace(d) greedily places each ball at the first position $\ge \text{lastPos} + d$ in $O(n)$. Binary search d over [1, pos.back() - pos[0]]! Time: $O(n \log(\text{Range}))$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int maxMinDistance(std::vector<int> pos, int k) {
std::sort(pos.begin(), pos.end());
auto canPlace = [&](int d) {
int placed = 1, last = pos[0];
for (size_t i = 1; i < pos.size(); ++i) {
if (pos[i] - last >= d) {
last = pos[i];
if (++placed == k) return true;
}
}
return false;
};
int lo = 1, hi = pos.back() - pos.front();
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPlace(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
int main() {
std::cout << maxMinDistance({1, 2, 3, 4, 7}, 3) << "\n"; // 3 (at 1, 4, 7)
return 0;
}
</details>
---