Chapter 84

Home

Binary Search on Answer

Not just for arrays — binary search works on any monotonic predicate. If you can answer "is value X feasible?" in O(F) time, you can binary search the optimal answer in O(F log range).

The Pattern

C++ — binary search on answer template

// Predicate: can we achieve value X?
bool feasible(int x) { /* O(F) check */ }

int lo = 0, hi = 1e9, ans = 0;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (feasible(mid)) {
        ans = mid;      // mid works, try higher
        lo = mid + 1;
    } else {
        hi = mid - 1;   // mid too high
    }
}
// ans is the maximum feasible value

💡 Classic example: split array into K subarrays minimising max sum

Binary search the maximum sum. For each mid, greedily count how many subarrays are needed. If count ≤ K, mid is feasible. O(N log sum).

Key Takeaways