Binary search on the answer

Prove monotone feasibility before searching

Taking shipping packages in their original order over multiple days as an example, the larger the capacity C, the number of days needed will not increase, so "can it be shipped within D days" is a condition that is false first and true later.

The lower bound of the capacity is the maximum single package weight, and the upper bound is the total weight. When judging, load packages in order, and start a new day when the capacity is exceeded; greedily loading as many consecutive packages as possible each day yields the minimum number of days under a fixed capacity.

Binary search the first feasible value within the integer capacity range. If one check is O(n) and the answer range size is V, the total time is O(n log V). A check without monotonicity cannot yield a reliable answer through binary search.

Minimum shipping capacity and extreme bounds

Example 1: Minimum capacity to ship packages in two days

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
    vector<int> w = {3, 2, 2, 4, 1};
    long long l = *max_element(w.begin(), w.end());
    long long r = accumulate(w.begin(), w.end(), 0LL);
    auto ok = [&](long long cap) {
        int days = 1; long long used = 0;
        for (int x : w) {
            if (used + x > cap) { ++days; used = 0; }
            used += x;
        }
        return days <= 2;
    };
    while (l < r) {
        long long m = l + (r - l) / 2;
        if (ok(m)) r = m; else l = m + 1;
    }
    cout << l << endl;
}

Output 7. Capacity 6 requires three days, while capacity 7 can be split into [3,2,2] and [4,1], so the minimum feasible value is 7.

Example 2: Upper and lower bounds and extreme days

With one day, the capacity must be at least the total weight. With at least one day per package, the minimum capacity equals the heaviest package.

These two boundaries can be used to check the program. Setting the lower bound to 0 without handling "a single item exceeds the capacity" will make the check function falsely report feasibility.

Tips

• First explain how feasibility changes as the answer grows, then choose the direction of the binary search update.
• This example does not allow rearranging packages; changing the order turns it into a different problem.
• The total weight and cumulative load may overflow int; use a wider integer type.

Prerequisites

• Binary search

Technical references

• C++ working draft: binary search

Scope note

This lesson is written by InfoCode and is not an official syllabus; the reference level is a site mapping and does not represent official levels, certification or eligibility. Practice records do not establish mastery or eligibility.

Reference level: GESP Level 5 (site mapping)

See contest pathways