🎯

Binary Search on Answer

Don't search the array — search the answer range. Set lo = min possible, hi = max possible, binary search for the boundary where isFeasible(mid) flips from false to true (or vice versa).

Optimization Feasibility Check Minimize Maximum Time O(n log k) Space O(1)

📋 When to Use

"Minimize the maximum" or "maximize the minimum"
Answer lies in a monotone feasibility space — once feasible stays feasible
Can write isFeasible(mid) in O(n) or O(n log n)
Keywords: minimum speed, max pages, ship within D days
Problem asks for a threshold value, not an index

💡 The key test: "If mid works, does mid−1 also work?" If yes → monotone → binary search on the answer space. The isFeasible function defines the binary predicate.

⚡ Complexity

Time

O(n log k)

Space

O(1)

O(log k) binary search iterations on the answer range k. Each iteration calls isFeasible in O(n). Total: O(n log k). No auxiliary space beyond a few variables.

Problem (LC #875) Koko has piles = [3, 6, 7, 11] bananas and h = 8 hours. Find the minimum eating speed ⚡k so she finishes within h hours. At speed k: hours per pile = ⌈pile/k⌉. Binary search on speed range [1..11]. If total hours ≤ h → ✅ feasible, try smaller. Else ❌ not feasible, try larger.
Answer: minimum speed = ⚡4 · 3 iterations of binary search

Step 1 / —

🎯 Compute Mid

✅ Feasible → save ans, hi = mid−1

❌ Not Feasible → lo = mid+1

🏆 Answer Found

🔍 Search Space — answer range [lo .. hi] · 🎯 mid · 🏆 saved ans

⚡ Feasibility Test — speed = —

◀ lo = 1

hi ▶ = 11

🎯 mid = —

🏆 ans = 11

Click ▶ Play or Next ▶ to begin

int lo = 1, hi = max(piles) = 11; int ans = hi;

Binary Search on Answer — Pattern SkeletonJAVA

// ── Binary Search on Answer ──────────────────────────────────────
int lo = minPossible, hi = maxPossible;
int ans = hi; // default to largest (minimize) or smallest (maximize)
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (isFeasible(mid)) {
        ans = mid;      // ✅ valid — try to do better (go smaller)
        hi = mid - 1;
    } else {
        lo = mid + 1;  // ❌ not valid — need more capacity
    }
}
return ans;

// isFeasible — Koko: can she eat all piles in h hours at speed k?
boolean isFeasible(int k) {
    int hours = 0;
    for (int pile : piles)
        hours += (pile + k - 1) / k; // ⌈pile/k⌉ using integer math
    return hours <= h;
}

🎯 Practice Problems

#875Koko Eating Bananas 🍌Medium #1011Capacity to Ship Packages Within D DaysMedium #1870Minimum Speed to Arrive on TimeMedium #2064Minimized Maximum of Products DistributedMedium #410Split Array Largest Sum — minimize the max partition sumHard GFGAllocate Minimum Number of PagesMedium