Binary Search on Answer – The Hidden Weapon in Competitive Programming

Hey Coders!

If you've ever struggled with problems where the constraints feel too large for brute force, yet too structured for standard binary search, you might be missing one powerful trick in your toolkit: Binary Search on Answer.

Problem Statement

You are given n books with pages[i] pages each. You want to distribute these books among k students such that:

Each student gets contiguous books.

The maximum number of pages assigned to a student is minimized.

Find the minimum value of the maximum pages that can be assigned to any student.

Constraints: - 1 <= n <= 10^5 - 1 <= pages[i] <= 10^4 - 1 <= k <= n

Intuition

At first glance, this seems greedy or DP. But notice the phrase "minimize the maximum" — this is a strong hint towards Binary Search on Answer.

Let’s understand what we are trying to minimize:
We want to minimize max_pages, i.e., the maximum number of pages assigned to a student.

Suppose we guess a value of max_pages = X.
Now, we try to check if we can assign books such that no student gets more than X pages. If yes, we try a smaller value. If not, we increase X.

This forms a monotonic function: - If X works, then all values greater than X also work.
- If X doesn’t work, all values smaller than X won’t work.

Approach

Define search space:

low = max(pages[i]) (no student can get fewer than the largest book)
high = sum(pages[i]) (one student takes all)

Binary Search:

For mid = (low + high)/2, check if it's feasible to allocate books with max pages = mid.
If yes, try smaller value (high = mid - 1)
If not, try larger value (low = mid + 1)