Parametric Search: Binary Searching the Answer Space & Feasibility Predicates

Optimization vs. Decision Duality (Megiddo's Parametric Search)

Many combinatorial optimization problems have the form:

Constructing the globally optimal schedule or partition from scratch can require dynamic programming in $O(N^2 K)$ time. Yet checking the decision problem—given a candidate threshold $X$, does there exist a valid configuration with cost $\le X$?—can often be solved by a simple $O(N)$ greedy scan! This reduction is valid whenever the feasibility predicate satisfies monotonicity:

• Minimization (False $\to$ True): If budget $X$ is sufficient, any larger budget $X' > X$ is also sufficient ($[F, F, \dots, F, T, T, \dots, T]$). We seek the first True.
• Maximization (True $\to$ False): If minimum separation $X$ is achievable, any smaller separation $X' < X$ is also achievable ($[T, T, \dots, T, F, F, \dots, F]$). We seek the last True.

Production C++20 Implementation: Discrete Min-Max Partition & Continuous 0-1 Fractional Search

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <vector>

// 1. Discrete Parametric Search: Split array w of non-negative ints into <= k contiguous subarrays
//    minimizing the maximum subarray sum. Time: O(N log(sum(w))), Space: O(1).
std::int64_t minimize_max_subarray_sum(const std::vector<std::int64_t>& w, std::size_t k) noexcept {
    std::int64_t lo = *std::max_element(w.begin(), w.end());
    std::int64_t hi = std::accumulate(w.begin(), w.end(), std::int64_t{0});

    auto feasible = [&](std::int64_t cap) noexcept -> bool {
        std::size_t buckets = 1;
        std::int64_t cur = 0;
        for (std::int64_t x : w) {
            if (cur + x > cap) {
                ++buckets;
                cur = x;
                if (buckets > k) return false; // Early exit!
            } else {
                cur += x;
            }
        }
        return true;
    };

    while (lo < hi) {
        const std::int64_t mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else               lo = mid + 1;
    }
    return lo;
}

// 2. Continuous Parametric Search (0-1 Fractional Programming):
//    Choose exactly k items to maximize (sum a_i) / (sum b_i) where b_i > 0.
double maximize_ratio_subset(const std::vector<double>& a,
                             const std::vector<double>& b,
                             std::size_t k) {
    const std::size_t n = a.size();
    double lo = 0.0, hi = 0.0;
    for (std::size_t i = 0; i < n; ++i) hi = std::max(hi, a[i] / b[i]);

    std::vector<double> residuals(n);
    // Fixed 64 iterations: immune to IEEE-754 ULP underflow infinite loops!
    for (int iter = 0; iter < 64; ++iter) {
        const double mid = lo + 0.5 * (hi - lo);
        for (std::size_t i = 0; i < n; ++i) {
            residuals[i] = a[i] - mid * b[i];
        }
        // Use O(N) Introselect (nth_element) instead of O(N log N) sort to sum top k residuals!
        std::nth_element(residuals.begin(),
                         residuals.begin() + static_cast<std::ptrdiff_t>(k),
                         residuals.end(),
                         std::greater<double>{});
        double top_k_sum = 0.0;
        for (std::size_t i = 0; i < k; ++i) top_k_sum += residuals[i];

        if (top_k_sum >= 0.0) lo = mid;
        else                  hi = mid;
    }
    return lo;
}