Binary Search on Answers — Crack the Hardest Problems in Log Time

🚀 Binary Search on Answers – The Complete Guide with Examples

📌 Introduction
Binary Search is not just for sorted arrays!
There’s a powerful pattern called "Binary Search on Answers" — where instead of searching inside an array, we search in the range of possible answers to a problem.

This technique is widely used in optimization problems like:

• Minimize the maximum workload
• Minimize days to finish a task
• Minimize the speed to complete something
• Allocate tasks with constraints

If your brute force approach is checking answers from 1 to maxPossibleValue, you can often replace it with Binary Search to drastically speed things up.

📖 Definition

Binary Search on Answers is an algorithmic technique where:

You define the search space as all possible values of the answer.

You check feasibility of a middle value using a helper function.

• `If the answer is possible, search the left half (to minimize).
• If the answer is not possible, search the right half (to increase).`

🪜 Naive Approach (Brute Force)

• Iterate over all possible values of the answer.
• For each value, check if it satisfies the problem constraints.
• Take the smallest valid value (or largest if maximizing).
• Drawback: Too slow when the answer space is huge (e.g., 1e9).

⚡ Optimized Approach (Binary Search)

• Instead of checking every answer, cut the search space in half each time.
• Use a helper function isFeasible() to check if the mid value works.
• Achieves O(log(maxPossibleValue) × N) time complexity.

⏳ Time & Space Complexity

Brute Force O(N × maxValue) O(1)
Optimized (BS) O(N × log(maxValue)) O(1)

💡 Example Problem – Koko Eating Bananas

Problem Statement

Koko loves to eat bananas. She can decide her eating speed k bananas/hour.
Given piles and h, find the minimum k to eat all bananas before guards return.

🛠 Brute Force Approach

cpp

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

// Check if Koko can eat all bananas at speed k in h hours
bool canEatAll(vector<int>& piles, int k, int h) {
    long long totalHours = 0;
    for (int bananas : piles) {
        totalHours += (bananas + k - 1) / k; // ceil division
    }
    return totalHours <= h;
}

int minEatingSpeedBruteForce(vector<int>& piles, int h) {
    int maxPile = *max_element(piles.begin(), piles.end());
    for (int k = 1; k <= maxPile; k++) {
        if (canEatAll(piles, k, h)) {
            return k;
        }
    }
    return maxPile;
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    int h = 8;
    cout << "Brute Force Result: " << minEatingSpeedBruteForce(piles, h) << endl;
    return 0;
}

⚡ Optimized Approach (Binary Search)

cpp

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

bool canEatAll(vector<int>& piles, int k, int h) {
    long long totalHours = 0;
    for (int bananas : piles) {
        totalHours += (bananas + k - 1) / k;
    }
    return totalHours <= h;
}

int minEatingSpeedOptimized(vector<int>& piles, int h) {
    int low = 1, high = *max_element(piles.begin(), piles.end());
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canEatAll(piles, mid, h)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    int h = 8;
    cout << "Optimized Result: " << minEatingSpeedOptimized(piles, h) << endl;
    return 0;
}

📝 Step-by-Step Explanation

• Define Search Space: Eating speed ranges from 1 to max(piles).
• Check Feasibility: If she can finish at speed mid, try smaller speed.
• Shrink Search Space: Binary search reduces the range quickly.

🔥 Important Practice Questions

• Koko Eating Bananas – LeetCode #875
• Capacity to Ship Packages Within D Days – LeetCode #1011
• Minimum Number of Days to Make m Bouquets – LeetCode #1482
• Split Array Largest Sum – LeetCode #410
• Book Allocation Problem – GFG

🤝 My Open Source Contribution

I’ve implemented these problems in my open-source GitHub repository:
📂 GitHub Repo: Check Out.

🎯 Key Takeaways

1. Use binary search on answers when brute force is iterating over possible values.

2. Always identify the search space & feasibility function.

3. It’s a game changer for optimization problems.`