Coding Interview Patterns

Binary Search on the Answer

When there's no array to search but the space of possible answers is monotonic — every value below some threshold fails, every value at or above it works — binary search over the answer itself instead of an index.

Applies whenever a yes/no predicate over a range of values is monotonic: false, false, …, false, true, true, …, true
Classic shapes: "minimum capacity to ship packages in D days," "Koko eating bananas," "minimize the maximum of k subarray sums"
The search space is the answer's value range, not array indices — bounds come from the problem (e.g. max single element to total sum), not 0 to n-1
Each feasibility check typically costs O(n) on its own, so total cost is O(n · log(range)), not O(log n)
The hard part is recognizing the monotonicity, not writing the binary search — the binary search shell itself is boilerplate once that's spotted

Minimum shipping capacity to deliver in D days

static int shipWithinDays(int[] weights, int days) {
    int lo = Arrays.stream(weights).max().getAsInt();   // must fit the heaviest single package
    int hi = Arrays.stream(weights).sum();               // one day, ship everything
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(weights, mid, days)) hi = mid;      // mid works — try smaller
        else lo = mid + 1;                                // mid too small — need more capacity
    }
    return lo;
}

static boolean feasible(int[] weights, int capacity, int days) {
    int daysNeeded = 1, currentLoad = 0;
    for (int w : weights) {
        if (currentLoad + w > capacity) { daysNeeded++; currentLoad = 0; }
        currentLoad += w;
    }
    return daysNeeded <= days;
}