Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D days

Search the answer, not the array

Nothing here is sorted, and there is no array to bisect. What there is, instead, is a candidate answer you can test in linear time: given a capacity, simulate the loading and count the days. Ship capacity is an integer in a bounded range, and the test is cheap, so you can bisect the range of possible answers rather than trying to construct the answer directly. This is the technique candidates most often fail to spot, and the reason is that every binary search they have written before operated on an input collection.

The cues are consistent enough to learn. Any phrasing of the form "minimise the maximum", "maximise the minimum", or "smallest value such that everything fits" is a candidate. So is any problem where the answer is a bounded number, checking a number is easy, and constructing the optimum looks like it needs dynamic programming you cannot formulate.

The predicate has to be monotone

Define feasible(c) as "capacity c delivers everything within D days". Bisection is only valid if the predicate, read across increasing c, is false for a while and then true forever. Argue it rather than assuming it: raising the capacity never forces the packing to start a day earlier, so the day count is non-increasing in c, so once c is feasible every larger c is too. The predicate is F F F F T T T T and you are looking for the boundary — the first T.

The bounds come from the problem, not from caution. The lower bound is max(weights), because a capacity below the heaviest package can never load it at all. The upper bound is sum(weights), which ships everything in a single day and is therefore known feasible. That last point matters: because hi is feasible, the answer definitely exists inside [lo, hi], which is what lets the loop return without a final existence check.

private static int daysNeeded(int[] weights, int cap) {
    int days = 1, load = 0;
    for (int w : weights) {
        if (load + w > cap) { days++; load = 0; }   // order is fixed, so just start a new day
        load += w;
    }
    return days;
}

That packing is greedy, and it is optimal because the order is fixed: leaving out a package that still fits today cannot possibly reduce the total number of days, since it only pushes work later. Worth saying out loud, because an interviewer who has seen this problem before will ask.

The loop and its invariant

int lo = 0, hi = 0;
for (int w : weights) { lo = Math.max(lo, w); hi += w; }

// Invariant: the answer is in [lo, hi]. Each iteration shrinks the range
// and never discards a value that could be the answer.
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;                    // overflow-safe, and mid < hi always
    if (daysNeeded(weights, mid) <= D) hi = mid;     // mid might be the answer: keep it
    else lo = mid + 1;                               // mid is infeasible: drop it
}
return lo;                                           // lo == hi: the first feasible capacity

Time is O(n · log(sum − max)) — one linear check per halving of the range — and space is constant. Note the shape of the complexity: the logarithm is over the magnitude of the answer, not over n, which is why this stays fast even when weights are large.

The five boundary conditions that make this bug-prone

These are the failures, in rough order of how often they appear on a whiteboard.

• Overflow. (lo + hi) / 2 overflows once lo + hi exceeds the integer range, and the bug survives every small test case. lo + (hi - lo) / 2 cannot overflow for non-negative bounds.
• Progress. With floor division, mid can equal lo but never equals hi. So hi = mid always shrinks the range, while lo = mid can leave it unchanged and spin forever. If your logic genuinely needs lo = mid, you must switch to a ceiling midpoint, lo + (hi - lo + 1) / 2. Floor pairs with hi = mid; ceiling pairs with lo = mid. Mixing them is the classic hang.
• Exactly one branch excludes mid. If both branches keep it the loop cannot terminate; if both exclude it you can step over the answer. Deciding which side owns mid is the same decision as first-true versus last-false, and it should be settled before you write the comparison.
• Existence. while (lo < hi) returning lo is only correct because hi was constructed to be feasible. Search a range where nothing may satisfy the predicate and you must test the returned value afterwards.
• Off-by-one in the bound itself. Setting lo to 0 instead of max(weights) is harmless here because infeasible values are correctly rejected; setting hi too low silently returns a wrong answer with no crash. Under-tight bounds cost logarithmic time, over-tight bounds cost correctness, so err loose.

Debug the invariant, not the comparison

The characteristic way this goes wrong in an interview is a candidate who writes the loop from memory, fails the sample, then starts perturbing it: < to <=, mid to mid + 1, lo to lo - 1, running the example again after each change. That process sometimes terminates in working code and it never terminates in an explanation, and interviewers read it as pattern recall with no model underneath.

The alternative costs one line of thought before any code: write down what the range means. Once you have committed to "the answer is in [lo, hi] and hi is known feasible", every branch is forced. mid feasible means the answer is at or below mid, so hi = mid. mid infeasible means the answer is strictly above, so lo = mid + 1. There is nothing left to guess, which is precisely why stating the invariant is worth more marks than the code it produces.

Say the invariant out loud before writing the loop, then derive each assignment from it. Candidates who tune comparison operators against the sample input are visibly guessing, and interviewers grade the difference.