Binary Search on Answer

Binary search can search more than arrays. If answers form a monotonic yes/no space, you can search the answer itself: too small fails, large enough succeeds, and the goal is the first feasible value.

The Monotonic Predicate

A predicate is a function that answers yes or no for a candidate answer. Binary search on answer works only when the predicate flips once: false false false true true true for minimum feasible problems, or true true false false for maximum feasible problems.

Scenario: Shipping Capacity

A warehouse must ship packages in order within D days. If truck capacity is too small, shipping fails. If capacity is larger, shipping succeeds. That monotonic property lets us search the minimum capacity that works.

Same Pattern in Java, Python, and JavaScript

This implementation returns the minimum capacity that ships packages in order within the required number of days.

class ShipCapacity {
    static int minCapacity(int[] weights, int days) {
        int left = 0, right = 0;
        for (int w : weights) { left = Math.max(left, w); right += w; }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, days, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    static boolean canShip(int[] weights, int days, int capacity) {
        int usedDays = 1, load = 0;
        for (int w : weights) {
            if (load + w > capacity) { usedDays++; load = 0; }
            load += w;
        }
        return usedDays <= days;
    }
}

Predicate Cost Matters

The total cost is not just O(log range). It is O(predicate_cost * log range). If checking feasibility scans n items, the complete complexity is O(n log range).

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Find the minimum capacity to ship packages within D days.
• Find the minimum eating speed to finish all piles within h hours.
• Split nums into at most k non-empty subarrays while minimizing the largest subarray sum.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class ShipWithinDays {
    static int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int weight : weights) { left = Math.max(left, weight); right += weight; }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, days, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    static boolean canShip(int[] weights, int days, int capacity) {
        int used = 1, load = 0;
        for (int weight : weights) {
            if (load + weight > capacity) { used++; load = 0; }
            load += weight;
        }
        return used <= days;
    }
}

class Koko { static int minSpeed(int[] piles, int h) { int l = 1, r = 0; for (int p : piles) r = Math.max(r, p); while (l < r) { int m = l + (r - l) / 2; if (can(piles, h, m)) r = m; else l = m + 1; } return l; } static boolean can(int[] piles, int h, int speed) { long hours = 0; for (int p : piles) hours += (p + speed - 1) / speed; return hours <= h; } }

class SplitArray { static int split(int[] nums, int k) { int l = 0, r = 0; for (int x : nums) { l = Math.max(l, x); r += x; } while (l < r) { int m = l + (r - l) / 2; if (parts(nums, m) <= k) r = m; else l = m + 1; } return l; } static int parts(int[] nums, int limit) { int count = 1, sum = 0; for (int x : nums) { if (sum + x > limit) { count++; sum = 0; } sum += x; } return count; } }

Solved modelWorked Interview Answer

Find the minimum truck capacity needed to ship packages within a fixed number of days. Capacity has a false-to-true feasibility boundary. Too-small capacity fails; larger capacity stays feasible.

class ShipWithinDays {
    static int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int weight : weights) { left = Math.max(left, weight); right += weight; }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, days, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    static boolean canShip(int[] weights, int days, int capacity) {
        int used = 1, load = 0;
        for (int weight : weights) {
            if (load + weight > capacity) { used++; load = 0; }
            load += weight;
        }
        return used <= days;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Using answer search without proving monotonicity.
• Choosing bounds that exclude the correct answer.
• Forgetting predicate cost in complexity.
• Returning the last tested mid instead of the converged boundary.
• Confusing minimum feasible with maximum feasible templates.

Execution guardrailQuick-Start Checklist

• Define candidate answer.
• Write the yes/no predicate.
• Prove false-to-true or true-to-false monotonicity.
• Set safe lower and upper bounds.
• Search for first feasible or last feasible deliberately.
• State O(predicate_cost * log range).

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice ship capacity, Koko bananas, minimum days to make bouquets, and split array largest sum.
• Review lower-bound binary search first.
• Study parametric search as an advanced form later.