Binary search on the answer

Some problems ask for the smallest (or largest) value that works, and finding it directly is hard, but checking whether a guess works is easy. If every value above a working one also works, binary search over the possible answers: each check halves the range.

Splitting work evenly

#include <iostream>
#include <vector>
using namespace std;

vector<int> jobs = {7, 2, 5, 8};

bool works(long long limit, int k) {
    int workers = 1;
    long long load = 0;
    for (int j : jobs) {
        if (j > limit) return false;
        if (load + j > limit) {
            workers++;
            load = 0;
        }
        load += j;
    }
    return workers <= k;
}

int main() {
    int k = 2;
    long long lo = 1, hi = 0;
    for (int j : jobs) hi += j;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (works(mid, k)) hi = mid;
        else lo = mid + 1;
    }
    cout << "the busiest worker needs " << lo << "\n";
    return 0;
}

Split the jobs, in order, among k workers so that the busiest worker has as little work as possible. Checking a guess limit is a greedy pass: give each worker jobs until the next one would exceed limit, and count the workers needed. A bigger limit never needs more workers, so the "works" values form a range, and binary search finds its smallest value. Watch lo and hi close in.

Each check is O(n) and there are about log₂(sum) checks, so the whole thing is O(n log(sum)), even for huge sums.

The pattern

lo = smallest possible answer, hi = largest possible answer
while lo < hi:
    mid = lo + (hi - lo) / 2
    if works(mid): hi = mid      (mid is fine; maybe smaller is too)
    else:          lo = mid + 1  (mid fails; the answer is bigger)
answer = lo

Mark lesson complete