This content originally appeared on DEV Community and was authored by M Umair Ullah
🚀 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
Use binary search on answers when brute force is iterating over possible values.
Always identify the search space & feasibility function.
It’s a game changer for optimization problems.`
This content originally appeared on DEV Community and was authored by M Umair Ullah
M Umair Ullah | Sciencx (2025-08-12T05:58:22+00:00) Binary Search on Answers — Crack the Hardest Problems in Log Time. Retrieved from https://www.scien.cx/2025/08/12/binary-search-on-answers-crack-the-hardest-problems-in-log-time/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.