AntInLoop

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>

---

Related Algorithms