Capacity to Ship Packages Within D Days (binary search on the answer).

Problem. Packages with given weights must ship in order within days days on one ship. Each day the ship loads packages (in their given sequence) up to its capacity. Find the minimum ship capacity that delivers everything within days.

Why this is binary search on the answer

Again, no array to search — we search the capacity. Feasibility is monotonic: if capacity C ships everything in days, any larger capacity does too (F F F T T T over increasing C). Binary-search the smallest feasible capacity.

Optimal — search the capacity, O(n log(sum))

The capacity range has a hard floor and ceiling: it must be at least max(weights) (a single package must fit), and never needs to exceed sum(weights) (ship everything in one day). For a candidate cap, greedily pack day by day and count the days used; feasible iff daysNeeded <= days.

int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) { lo = Math.max(lo, w); hi += w; }  // [max, sum]

    while (lo < hi) {
        int cap = lo + (hi - lo) / 2;
        if (daysNeeded(weights, cap) <= days) hi = cap;  // fits -> try smaller capacity
        else lo = cap + 1;                                // doesn't fit -> need more
    }
    return lo;                                            // minimum feasible capacity
}

private int daysNeeded(int[] weights, int cap) {
    int days = 1, load = 0;
    for (int w : weights) {
        if (load + w > cap) { days++; load = 0; }  // start a new day
        load += w;                                  // packages must ship IN ORDER
    }
    return days;
}

O(n log(sum(weights))) time — log(sum) search steps, each an O(n) greedy pack — and O(1) space.

The two details

lo = max(weights) is not optional: a capacity below the heaviest package can never ship it, and starting lo at 1 would let the feasibility check loop forever or report impossible. And packages ship in their given order — the greedy fills the current day until the next package overflows cap, then opens a new day, never reordering.