Binary Search on Answers — The Secret Weapon for Many Hard Problems

📌 Introduction

When we think about binary search, the first thing that comes to mind is searching for a target in a sorted array. But binary search is much more powerful than that — it can be used even when the array isn’t explicitly given but the answer space is sorted. This technique is called Binary Search on Answers (or Search Space Binary Search).

In this blog, we’ll explore:

• What Binary Search on Answers is

• Naive approach vs. optimized approach

• Time & space complexities

• Example problems

• Open-source contributions

---

🔍 Definition

Binary Search on Answers is a problem-solving technique where:

• The solution lies within a range (e.g., [low, high]).

• The validity of a solution can be checked with a feasibility function.

• If a solution works, all larger (or smaller) solutions may also work (monotonicity property).

We then apply binary search over the range of possible answers to find the optimal one.

---

💡 Example Problem — Koko Eating Bananas

---

📍 Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards leave and will come back in h hours.
Koko can decide her eating speed k bananas/hour. Find the minimum k such that she can eat all the bananas before the guards come back.

---

🚶‍♂️ Brute Force Approach

• Try every possible eating speed from 1 to max(piles).

• For each speed, check if she can finish all bananas in h hours.

• Return the smallest valid speed.

Time Complexity: O(N × maxPile)
Space Complexity: O(1)

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

// Function to 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 on Answers

• Instead of checking all speeds, search in the range [1, maxPile] using binary search.

• At each step:

  • Check if speed mid is enough.

  • If yes, try smaller speeds.

  • If no, try bigger speeds.

Time Complexity: O(N × log(maxPile))
Space Complexity: O(1)

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

// Same helper function to check feasibility
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; // Try smaller speeds
        } else {
            low = mid + 1; // Need bigger speed
        }
    }
    return low;
}

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

---

💬 Explanation for Readers

• Brute Force: Tries every possible answer → very slow if the answer space is huge.

• Optimized: Uses binary search to shrink the search space in logarithmic steps.

If maxPile = 1e9,

• Brute force → ~1e9 checks × N (impossible)

• Optimized → log₂(1e9) ≈ 30 checks × N (very fast)

---

🛠 Example Problems

Here’s the intuition for a few famous problems:

1. Koko Eating Bananas 🐵

   • Search space: [1, max pile size]

   • Feasibility: Can Koko eat all bananas in h hours at speed mid?

2. Capacity to Ship Packages Within D Days 📦

   • Search space: [max weight, total weight]

   • Feasibility: Can we ship all packages in D days with capacity mid?

3. Minimum Number of Days to Make m Bouquets 🌸

   • Search space: [min bloom day, max bloom day]

   • Feasibility: Can we make m bouquets in mid days?

4. Split Array Largest Sum 📊

   • Search space: [max element, sum of array]

   • Feasibility: Can we split into ≤ k subarrays with max sum ≤ mid?

---

📚 Time & Space Complexity Table

---

🔥 Important Practice Questions

1. Koko Eating Bananas — LeetCode #875

2. Capacity to Ship Packages Within D Days — LeetCode #1011

3. Minimum Number of Days to Make m Bouquets — LeetCode #1482

4. Split Array Largest Sum — LeetCode #410

5. Allocate Minimum Number of Pages — GFG Problem

---

🤝 My Open-Source Contribution

I’ve implemented several Binary Search on Answers problems in C++ and made them available for the community.

🔗 GitHub Repository: https://github.com/UmairDevloper/DSA-in-C-.git
📂 Folder: /binary-search-on-answers

---

🧠 Final Tips

• Always check monotonicity before applying Binary Search on Answers.

• Carefully choose low and high bounds.

• The feasibility function should be O(N) or faster for efficiency.

🏷 Tags

#BinarySearch #Algorithms #CompetitiveProgramming #DataStructures #DSA #ProblemSolving #LeetCode #C++ #CodingInterview