Binary search on the answer

Binary-search the space of ANSWERS, not an array. Optimization → repeated yes/no decision.

The reframe

• Hard: "what's the smallest largest-part sum when splitting into k?"
• Easy: "can we split into ≤ k parts each ≤ L?" (greedy check)
• The check is MONOTONE in L: once feasible, stays feasible
• So answers are sorted by feasibility → binary-search the threshold

Watch it search the answer space

Split [7,2,5,10,8] into 2. Candidate limits 10..32; green = feasible, red = not. Converges on 18: [7,2,5]=14, [10,8]=18.

Log vs linear checks

Range ~2M: scan every candidate = 228,000 checks; binary search = 20. Doubling the range adds ONE check.

Requirements + traps

• Predicate must be MONOTONE — prove it, or it converges on nonsense
• Bracket the bounds correctly (low infeasible, high feasible)
• min-feasible vs max-feasible needs different update rules (ceiling mid!)
• Real-valued answer → iterate to a tolerance
• Often "binary search wrapped around greedy"

Takeaway

Binary search only needs a monotone predicate — a sorted array is just one case. "Optimize" often reduces to "decide, repeatedly." Next tier: advanced & probabilistic structures.