Binary-search a monotone feasibility predicate
Binary search can find the smallest feasible answer when feasibility changes once from false to true. For example, determine the minimum daily capacity needed to finish sequential workloads within a fixed number of days.
fun daysNeeded(workloads: IntArray, capacity: Long): Int {
require(workloads.all { it > 0 })
require(capacity >= (workloads.maxOrNull()?.toLong() ?: 0L))
if (workloads.isEmpty()) return 0
var days = 1
var used = 0L
for (work in workloads) {
if (used + work > capacity) { days++; used = 0 }
used += work
}
return days
}
Increasing capacity cannot increase required days, establishing monotonicity. Search from the largest item to the total sum, using Long for capacities and totals.
Acceptance checks
For workloads [3,2,2] and two days, minimum capacity is four. Test one day, one item per day, empty input, and invalid nonpositive day limits. Compare small cases against exhaustive capacity enumeration.
Check: prove monotonicity before writing the binary-search loop; a fast search over a nonmonotone predicate has no correctness guarantee.