Binary Search on Answer Space: Allocation & Feasibility Checks0%
Elementary Sorting Algorithms: Bubble, Selection & Insertion Sort (O(n²))

Binary Search on Answer Space: Allocation & Feasibility Checks

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Binary Search on Answer Space: Allocation & Feasibility Checks

While traditional binary search finds a value within an explicit sorted array, advanced technical interview problems apply binary search to an abstract range of numerical answers (the "Answer Space"). This paradigm solves optimization problems like "Capacity to Ship Packages Within D Days", "Koko Eating Bananas", and "Book Allocation" in $O(n \log(\text{range}))$ time.

1. Real-World Analogy: Tuning the Perfect Water Faucet Temperature

Imagine adjusting the knob on a shower to find the exact temperature you can tolerate:

  • You don't test every single degree between 0°C and 100°C one by one.
  • You turn the knob to the middle (50°C). It is scalding hot (Infeasible).
  • You know that every temperature above 50°C will also be scalding hot! You instantly eliminate the entire upper half.
  • You turn the knob down to 25°C. It's too cold. You narrow your range to 25°C–50°C.
  • You are binary searching a monotonic feasibility function!

2. When Can You Binary Search the Answer?

You can apply Binary Search on the Answer Space if the problem satisfies the Monotonicity Condition: $$\text{If an answer } X \text{ is feasible, then every value } > X \text{ (or } < X\text{) is guaranteed to be feasible!}$$

Output
Speed / Capacity: 1 2 3 4 5 6 7 8 9 10
Feasible in D Days? F F F F T T T T T T
^
MINIMUM FEASIBLE CAPACITY!

3. Classic Problem: Capacity To Ship Packages Within D Days

A conveyor belt has packages with weights weights[i]. We must ship all packages within days days. Packages must be loaded in order, and each day's total weight cannot exceed the ship's weight capacity. Return the minimum weight capacity of the ship.

The Algorithm:

  1. 1
    Search Space:
  • Minimum possible capacity: max(weights) (the ship must carry at least the heaviest single item!).
  • Maximum possible capacity: sum(weights) (shipping everything in 1 day).
  1. 1
    Feasibility Function (can_ship_in_days(capacity)):
  • Greedily pack items into the current day until exceeding capacity. Count total days required.
  • If days_needed <= days, return True; else False.

4. Multi-Language Implementations: Shipping Capacity

Python 3:

Python
def ship_within_days(weights: list[int], days: int) -> int:
# 1. Define the monotonic answer search space
low = max(weights)
high = sum(weights)
ans = high
# 2. Feasibility helper function
def can_ship(capacity: int) -> bool:
days_needed = 1
current_load = 0
for w in weights:
if current_load + w > capacity:
days_needed += 1
current_load = 0
current_load += w
return days_needed <= days
 
# 3. Binary search for minimum feasible capacity
while low <= high:
mid = low + (high - low) // 2
if can_ship(mid):
ans = mid # Mid is feasible! Try searching for a smaller capacity
high = mid - 1
else:
low = mid + 1 # Not feasible, ship must be bigger
return ans

Modern JavaScript / TypeScript:

TypeScript
export function shipWithinDays(weights: number[], days: number): number {
let low = Math.max(...weights);
let high = weights.reduce((a, b) => a + b, 0);
let ans = high;
 
function canShip(capacity: number): boolean {
let daysNeeded = 1;
let currentLoad = 0;
for (const w of weights) {
if (currentLoad + w > capacity) {
daysNeeded++;
currentLoad = 0;
}
currentLoad += w;
}
return daysNeeded <= days;
}
 
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (canShip(mid)) {
ans = mid;
high = mid - 1; // Try smaller capacity
} else {
low = mid + 1; // Increase capacity
}
}
 
return ans;
}

5. Trace Table: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5

  • low = max(weights) = 10
  • high = sum(weights) = 55
IterationlowhighmidDays Needed with Capacity midFeasible? (<= 5)Action
11055322 daysYesans = 32, high = 31
21031204 daysYesans = 20, high = 19
31019145 daysYesans = 14, high = 13
41013118 daysNolow = 12
51213127 daysNolow = 13
61313136 daysNolow = 14 (terminates)

Final Result: Minimum feasible capacity is 15 (or verified at 15)!

Interactive Quiz

Multiple Choice Questions

Question 1
What core mathematical property must a feasibility function exhibit to allow Binary Search on Answer Space?
Question 2
In "Capacity to Ship Packages Within D Days", why is the lower bound of the search space initialized to max(weights)?
Question 3
What is the time complexity of the Binary Search on Answer Space for shipping packages, where $N$ is the number of packages and $W = \text{sum(weights)} - \text{max(weights)}$?
Question 4
When the feasibility function returns True while searching for the minimum possible valid capacity, how should the binary search bounds be updated?
Question 5
Which of the following problems can be framed as Binary Search on Answer Space?
Next Lesson

Elementary Sorting Algorithms: Bubble, Selection & Insertion Sort (O(n²))

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Binary Search: Search Space Elimination, Lower Bound & Upper BoundElementary Sorting Algorithms: Bubble, Selection & Insertion Sort (O(n²))

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext