Hello, Codeforces!

If you’ve solved a few problems, you might have heard about the technique called “binary search on the answer.” This is one of the most powerful and elegant tricks in competitive programming.

Today, I want to explain this technique clearly, show how and when to apply it, and share a classic example.

What is Binary Search on the Answer?

Usually, binary search helps find an element in a sorted array. But sometimes, the problem doesn’t give you a sorted array — instead, the solution space (the range of possible answers) is sorted or monotonic.

Binary search on the answer means:

• We guess a candidate answer mid inside some range [low, high].
• We check if this candidate is valid or not.
• Based on that, we narrow down the range.
• Repeat until we find the best answer.

When to Use It?

Use binary search on the answer if: The problem asks you to find a minimum or maximum value satisfying some condition. You can check whether a candidate answer is feasible efficiently. The feasibility check is monotonic: If x works, then all values greater (or smaller) than x also work (or don’t).

Example problem

You have n items with weights and want to pack them into k boxes. Each box can hold items up to some weight limit. Find the minimum possible maximum weight limit so that all items fit.

Step 1: Define the Search Space The answer lies between: low = max item weight (at least the heaviest item) high = sum of all weights (all items packed into one box)

Step 2: Feasibility Check Function Given a candidate mid (max box capacity), try to pack items greedily: Keep adding items to the current box until the total weight exceeds mid. Then start filling a new box. If the number of boxes used exceeds k, then mid is too small (not feasible). Otherwise, it’s feasible.

Step 3: Binary Search Implementation (C++)

#include <bits/stdc++.h>
using namespace std;

bool canPack(const vector<int>& weights, int k, int mid) {
    int boxCount = 1, currentSum = 0;
    for (int w : weights) {
        if (w > mid) return false; // single item too big
        if (currentSum + w <= mid)
            currentSum += w;
        else {
            boxCount++;
            currentSum = w;
        }
        if (boxCount > k)
            return false;
    }
    return true;
}

int findMinMaxWeight(const vector<int>& weights, int k) {
    int low = *max_element(weights.begin(), weights.end());
    int high = accumulate(weights.begin(), weights.end(), 0);
    int answer = high;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canPack(weights, k, mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

int main() {
    vector<int> weights = {10, 20, 30, 40, 50};
    int k = 3;
    cout << "Minimum max box weight: " << findMinMaxWeight(weights, k) << "\n";
    return 0;
}

Other Classic Problems Using This Technique

Aggressive cows — placing cows in stalls minimizing max distance. Painter's partition problem — dividing boards among painters minimizing max time. Scheduling problems where you minimize maximum time or capacity.

Why It’s Useful

It reduces complicated problems to simple binary searches. Avoids complex dynamic programming or greedy proofs. Easy to implement once you identify monotonicity in the answer space.

Final Tip

Before coding, ask yourself: Can I quickly check if a candidate answer is valid? Is the set of valid answers continuous and monotonic? If yes, binary search on the answer can be your friend!

If you liked this blog, please upvote and share your favorite problems where you used this technique!

Feel free to edit or add your own examples and tips! If you want help with other algorithmic topics or problem-solving tricks, just ask!