Data Structures & AlgorithmsBinary Search on Answer Space

Binary Search on Answer Space

LevelAdvanced

Duration90 mins

TopicBinary Search on Answer Space

1 / 4

When the Search Target Is an Answer, Not an Element

Beyond Array Lookups: A New Dimension of Binary Search

You've mastered binary search for finding elements in a sorted array. Given [1, 3, 5, 7, 9] and target 5, you can locate it in O(log n) time. But what happens when there's no array to search—when the 'answer' isn't stored anywhere, but rather needs to be discovered?

Consider this problem:

You have a conveyor belt carrying packages to be shipped within D days. Each package has a weight, and packages must be shipped in order. What is the minimum ship capacity needed to ship all packages within D days?

There's no array containing 'ship capacities to check.' The answer is a value that must satisfy certain constraints. Yet binary search applies here with devastating efficiency. This page introduces this paradigm shift—from searching elements to searching answer values.

What You Will Learn

By the end of this page, you will understand: (1) the conceptual leap from element-search to answer-search, (2) how continuous or discrete solution spaces become searchable, (3) why this technique is called 'binary search on answer' and not optimization, and (4) the mental framework for recognizing these problems instantly.

The Traditional Binary Search Mental Model

Before we extend binary search, let's crystallize what traditional binary search actually does. Understanding its essence reveals why the extension is natural.

Traditional binary search has three components:

Search Space: A sorted array containing potential answers
Target: A specific value you're looking for
Comparison Logic: Determines whether to go left or right

When you search for value x in array [1, 3, 5, 7, 9], you're asking: 'Where does x appear?' The array is explicit—every candidate is laid out before you.

traditional_binary_search.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def binary_search(arr: list[int], target: int) -> int:
    """
    Traditional binary search: find target in sorted array.
    Returns index if found, -1 otherwise.
    
    Search Space: arr[left..right]
    Target: specific value to find
    Logic: compare arr[mid] to target
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid  # Found it!
        elif arr[mid] < target:
            left = mid + 1  # Target is to the right
        else:
            right = mid - 1  # Target is to the left
    
    return -1  # Not found
 
# Example usage
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5))  # Output: 2 (index of 5)
print(binary_search(arr, 6))  # Output: -1 (not in array)

The key insight: Binary search works because the array is sorted, meaning there's a monotonic relationship. All elements to the left of x are smaller; all elements to the right are larger. This ordering allows us to eliminate half the search space with each comparison.

But here's the critical observation: the sortedness of an array is just one instance of a broader principle. Binary search works on any search space where a monotonic property allows us to eliminate half the candidates at each step.

The Core Principle

Binary search doesn't require an array. It requires a range with a monotonic property: a condition that changes from false to true (or true to false) exactly once as you move through the range. This is the secret that unlocks binary search on answer space.

The Paradigm Shift: From Elements to Answers

Now, let's make the conceptual leap. Instead of searching an array for an element, we search a range of values for an optimal answer.

The new mental model:

Traditional Binary Search	Binary Search on Answer Space
Search space: array elements	Search space: range of possible answers
Searching for: where target appears	Searching for: optimal feasible value
Comparison: `arr[mid] vs target`	Comparison: `canAchieve(mid)` (feasibility check)
Output: index of target	Output: the answer value itself

The profound insight is that the answer space itself becomes the 'array'. If possible answers range from 1 to 1,000,000, we binary search this range—not by comparing array values, but by checking whether each candidate answer is feasible.

Traditional: Search for Element

•Array: [1, 3, 5, 7, 9]
•Target: 5
•Question: 'Is arr[mid] equal to 5?'
•Answer: The index where 5 lives
•Search space: explicitly stored

New: Search for Answer

•Range: [1, 1000000]
•Target: minimum feasible capacity
•Question: 'Can we ship with capacity mid?'
•Answer: The capacity value itself
•Search space: implicitly defined

The feasibility function replaces the comparison. In traditional search, we compare arr[mid] to the target. In answer-space search, we ask: 'Is this candidate answer achievable?' or 'Does this value satisfy all constraints?'

This is why the technique is sometimes called 'binary search the answer' or 'binary search on solution space'. We're not searching for where something is stored—we're searching for a value that optimizes an objective while satisfying constraints.

Why 'Binary Search on Answer Space'?

The name emphasizes that you're searching a space of possible answers (like ship capacities, maximum distances, or time limits), not a data structure. The 'answer' is what you output—the optimal value that solves the problem.

The Implicit Search Space

In traditional binary search, the search space is explicit: an array physically exists in memory. In answer-space binary search, the search space is implicit: it's a conceptual range of values, not a stored data structure.

Defining the implicit search space:

For any answer-space problem, you must determine:

Lower Bound (lo): The smallest possible answer
Upper Bound (hi): The largest possible answer

These bounds come from problem constraints and logical reasoning. The 'array' you're searching is conceptually [lo, lo+1, lo+2, ..., hi] (for integers) or a continuous interval [lo, hi] (for real numbers).

Ship Packages Problem — Defining BoundsGiven packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and D = 5 days, find minimum ship capacity.

Input

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], D = 5

Output

Minimum capacity = 15

Explanation

Lower bound: max(weights) = 10. (Ship must hold at least the heaviest package.) Upper bound: sum(weights) = 55. (Worst case: ship everything in 1 day.)

Search space: [10, 55] — 46 candidates instead of checking all possibilities.

With binary search: log₂(46) ≈ 6 checks instead of 46 linear checks.

Why bounds matter tremendously:

Choosing tight bounds is crucial for efficiency and correctness:

Too tight lower bound: You might miss the correct answer
Too loose upper bound: You waste search iterations
Just right: Minimal iterations, guaranteed correctness

For the shipping problem:

Lower bound max(weights) is necessary because the ship must fit the heaviest single package
Upper bound sum(weights) is sufficient because we could always ship everything in one day

This gives us a finite, bounded search space that binary search can efficiently explore.

defining_search_bounds.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def find_search_bounds_shipping(weights: list[int]) -> tuple[int, int]:
    """
    Determine the implicit search space for shipping problem.
    
    Lower bound: Must fit the heaviest package
    Upper bound: Ship everything at once (worst case)
    """
    lower_bound = max(weights)  # Can't be smaller than largest package
    upper_bound = sum(weights)  # Could ship all in 1 day
    
    return lower_bound, upper_bound
 
# Example
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
lo, hi = find_search_bounds_shipping(weights)
print(f"Search space: [{lo}, {hi}]")  # [10, 55]
print(f"Search space size: {hi - lo + 1}")  # 46 candidates
print(f"Binary search checks: ~{(hi - lo + 1).bit_length()}")  # ~6 checks

Bound Selection Is Problem-Specific

There's no universal formula for bounds. Each problem requires careful analysis. For minimization problems, the lower bound is the smallest theoretically possible value; for maximization, the upper bound is the largest. Incorrect bounds lead to wrong answers or missed optima.

The Feasibility Predicate: The Heart of the Algorithm

The feasibility predicate is the function that replaces array comparison. Given a candidate answer mid, it returns:

True: This answer works (satisfies all constraints)
False: This answer doesn't work (violates at least one constraint)

This function is the most important piece of any answer-space binary search solution. Its correctness determines algorithm correctness; its efficiency determines overall time complexity.

Designing the feasibility predicate:

The predicate must answer a yes/no question: 'Can we achieve the goal with answer = mid?' For the shipping problem: 'Can we ship all packages in D days with capacity = mid?'

feasibility_predicate.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def can_ship_in_d_days(weights: list[int], D: int, capacity: int) -> bool:
    """
    Feasibility predicate for shipping problem.
    
    Question: Can we ship all packages in D days with given capacity?
    
    Strategy: Greedily load each day until capacity is reached.
    Count days needed; return True if days_needed <= D.
    
    Time Complexity: O(n) where n = len(weights)
    """
    days_needed = 1  # Start with day 1
    current_load = 0  # Current day's load
    
    for weight in weights:
        # If this package fits in current day's ship
        if current_load + weight <= capacity:
            current_load += weight
        else:
            # Start a new day
            days_needed += 1
            current_load = weight
            
            # Early termination: already exceeds D
            if days_needed > D:
                return False
    
    return days_needed <= D
 
# Example usage
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
D = 5
 
print(can_ship_in_d_days(weights, D, 10))  # False (needs 10 days)
print(can_ship_in_d_days(weights, D, 15))  # True (needs exactly 5 days)
print(can_ship_in_d_days(weights, D, 20))  # True (needs 4 days)
print(can_ship_in_d_days(weights, D, 55))  # True (needs 1 day)

Critical properties of the feasibility predicate:

Deterministic: Same input always gives same output
Efficient: Usually O(n) or O(n log n); otherwise binary search gains are lost
Monotonic with respect to the search space: This is essential for binary search to work

The monotonic property means:

If canAchieve(x) is True, then canAchieve(x+1) is also True (for minimization)
If canAchieve(x) is False, then canAchieve(x-1) is also False (for minimization)

This creates a clean boundary in the search space: all values below some threshold are infeasible; all values at or above are feasible.

Predicate Design Principle

Always make the predicate answer a simple yes/no question about feasibility. Complex predicates with multiple return values or special cases introduce bugs. If you find yourself returning -1, 0, or 1, you're likely overcomplicating the design.

Visualizing the Search Space Partition

Binary search on answer space works because the feasibility predicate partitions the search space into two contiguous regions:

[lo .................... X .................... hi]
 |←— INFEASIBLE —→|←——— FEASIBLE ———→|

For minimization problems (finding smallest feasible answer):

All values less than the optimal answer X are infeasible
All values ≥ X are feasible
We want to find X, the first feasible value

For maximization problems (finding largest feasible answer):

All values ≤ X are feasible
All values greater than X are infeasible
We want to find X, the last feasible value

Shipping Problem: Feasibility Across Answer Space
Capacity	Days Needed	Feasible (D=5)?	Region
10	10 days	❌ False	INFEASIBLE
11	9 days	❌ False	INFEASIBLE
12	8 days	❌ False	INFEASIBLE
13	6 days	❌ False	INFEASIBLE
14	6 days	❌ False	INFEASIBLE
15	5 days	✓ True	BOUNDARY (Answer)
16	5 days	✓ True	FEASIBLE
20	4 days	✓ True	FEASIBLE
30	3 days	✓ True	FEASIBLE
55	1 day	✓ True	FEASIBLE

Notice the clean partition: every capacity below 15 is infeasible, and every capacity at or above 15 is feasible. The answer is 15—the boundary point where feasibility changes.

Binary search finds this boundary efficiently by:

Checking the midpoint mid
If mid is feasible, the answer is at mid or to its left (for minimization)
If mid is infeasible, the answer is to the right of mid
Repeat until the boundary is found

This is exactly like finding the first True value in an array [False, False, False, False, False, True, True, True, ...].

The Partition Must Be Clean

If the feasibility function doesn't create a clean partition (e.g., True, False, True, False randomly), binary search won't work. This is why verifying the monotonic property is essential before applying this technique.

The Complete Algorithm Template

Now let's assemble all the pieces into a complete algorithm. The template applies to virtually all 'binary search on answer' problems:

Algorithm structure:

Define search bounds: lo = minimum possible answer, hi = maximum possible answer
Define feasibility predicate: canAchieve(mid) returns True/False
Binary search to find the optimal boundary point
Return the answer

binary_search_on_answer_template.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def binary_search_on_answer(lo: int, hi: int, is_feasible) -> int:
    """
    Generic template for binary search on answer space.
    
    This finds the MINIMUM feasible value (for minimization problems).
    
    Args:
        lo: Lower bound of answer space
        hi: Upper bound of answer space  
        is_feasible: Predicate function (answer) -> bool
        
    Returns:
        The minimum value x such that is_feasible(x) == True
        
    Invariant: 
        - All values < answer are infeasible
        - All values >= answer are feasible
        
    Time Complexity: O(log(hi - lo) * cost_of_is_feasible)
    """
    answer = hi  # Default to upper bound (always feasible)
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if is_feasible(mid):
            # mid works! But maybe something smaller also works
            answer = mid  # Record this as best so far
            hi = mid - 1  # Search for smaller feasible value
        else:
            # mid doesn't work; need larger value
            lo = mid + 1
    
    return answer
 
 
def ship_within_days(weights: list[int], D: int) -> int:
    """
    Complete solution: Find minimum ship capacity to ship packages in D days.
    
    LeetCode 1011: Capacity To Ship Packages Within D Days
    """
    # Step 1: Define search bounds
    lo = max(weights)   # Must fit largest package
    hi = sum(weights)   # Could ship all at once
    
    # Step 2: Define feasibility predicate
    def can_ship(capacity: int) -> bool:
        days_needed = 1
        current_load = 0
        for weight in weights:
            if current_load + weight <= capacity:
                current_load += weight
            else:
                days_needed += 1
                current_load = weight
        return days_needed <= D
    
    # Step 3: Binary search for minimum feasible capacity
    return binary_search_on_answer(lo, hi, can_ship)
 
 
# Example usage
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
D = 5
print(f"Minimum capacity: {ship_within_days(weights, D)}")  # Output: 15

Complexity analysis:

Binary search iterations: O(log(hi - lo))
Each iteration: O(n) for the feasibility check
Total time: O(n × log(hi - lo))

For the shipping problem with weights summing to S:

Search space: O(S) values
Total time: O(n × log S)

This is dramatically better than brute force, which would try every capacity and take O(S × n) time.

Template Variations

For maximization problems, swap the logic: when feasible, search right (lo = mid + 1); when infeasible, search left (hi = mid - 1). The answer becomes the last feasible value rather than the first.

Recognizing Answer-Space Binary Search Problems

The key skill is recognizing when a problem can be solved with binary search on answer—even when the problem statement doesn't mention search at all. Here are the telltale signs:

Recognition Patterns

•Optimization language: 'Minimize the maximum X' or 'Maximize the minimum Y' — classic indicator of answer-space search
•Bounded answer range: The answer must lie within a finite, known range that you can determine from constraints
•Feasibility can be checked: Given a candidate answer, you can efficiently determine if it's achievable
•Monotonic feasibility: If answer X works, then X+1 definitely works (or vice versa for max problems)
•Keywords: 'minimum capacity', 'maximum distance', 'smallest time', 'largest possible', 'at most K', 'within D days'
•Constraint satisfaction: The problem asks for a value that satisfies multiple constraints simultaneously

The mental transformation:

Original problem:

'What is the minimum X such that [conditions are satisfied]?'

Transformed to binary search:

'For a given X, can [conditions be satisfied]? Binary search to find the smallest such X.'

This transformation turns an optimization problem into a decision problem. Binary search then efficiently explores the decision space.

Good Fit for Answer-Space Search

•Minimum ship capacity
•Maximum minimum distance between points
•Smallest largest sum when splitting array
•Minimum time to complete all tasks
•Maximum number of items with budget

NOT Suitable for This Technique

•Find all valid answers (not optimization)
•Non-monotonic feasibility
•Discrete choices without ordering
•Answer depends on path, not just value
•Feasibility check is exponential

The Reframing Trick

When you see an optimization problem, ask: 'If I knew the answer was X, could I verify it easily?' If yes, you likely have a binary search on answer problem. The verification becomes your feasibility predicate.

Common Mistakes and Pitfalls

Binary search on answer space is powerful but error-prone. Here are the most common mistakes and how to avoid them:

Pitfall Catalog

•Wrong bounds: Setting lo too high or hi too low causes missing the optimal answer. Always err on the side of wider bounds if unsure, then tighten based on problem analysis.
•Non-monotonic predicate: If your feasibility function isn't monotonic (flips between True/False multiple times), binary search will fail silently. Always verify monotonicity before implementing.
•Incorrect boundary logic: Confusing when to search left vs. right, or when to update the answer. Use the invariant: 'answer is the smallest (or largest) feasible value seen so far.'
•Off-by-one errors: The classic binary search bug. Ensure your loop condition (lo <= hi vs lo < hi) matches your update logic (mid + 1 vs mid).
•Inefficient feasibility check: If the predicate is O(n²) and search space is O(S), total time is O(n² log S)—possibly worse than brute force! Keep predicates efficient.
•Integer overflow in bounds: When searching large ranges (e.g., up to 10⁹), ensure lo + hi doesn't overflow. Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2.

common_bug_examples.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# ❌ WRONG: Bounds too tight - might miss answer
def bad_bounds(weights, D):
    lo = min(weights)  # Wrong! Must be >= max(weights)
    hi = sum(weights) // D  # Wrong! Might need more capacity
    # ... this fails for many inputs
 
# ❌ WRONG: Incorrect update logic
def bad_update_logic(lo, hi, is_feasible):
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_feasible(mid):
            lo = mid  # BUG: Never terminates! lo never moves up
        else:
            hi = mid - 1
    return lo
 
# ✓ CORRECT: Proper minimization template
def correct_minimization(lo, hi, is_feasible):
    answer = hi
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            answer = mid
            hi = mid - 1  # Try smaller
        else:
            lo = mid + 1  # Need larger
    return answer

Debug Strategy

When your solution fails, first verify: (1) Are bounds definitely correct? Test at boundaries. (2) Does the predicate correctly say True/False? Test manually on examples. (3) Does feasibility have the monotonic property? Check a few consecutive values.

Summary: The Answer-Space Paradigm

We've covered a major conceptual expansion of binary search. Let's consolidate the key ideas:

Key Takeaways

•Binary search works on any monotonic search space — not just arrays. The 'sortedness' of arrays is just one instance of monotonicity.
•Answer-space search has implicit search space — ranges like [min_possible, max_possible] rather than stored elements.
•The feasibility predicate is the core — a function that answers 'Is this candidate answer achievable?' The predicate must be efficient and monotonic.
•Feasibility partitions the search space — into infeasible (below boundary) and feasible (at/above boundary). We find the boundary.
•Recognition comes from problem structure — 'minimize maximum', 'find smallest X such that', bounded answers, and verifiable constraints all signal answer-space search.
•Complexity is O(log(range) × predicate_cost) — often O(n log S) where S is the answer-space size.

What's next:

Now that you understand the paradigm shift from element-search to answer-search, the next page explores monotonic functions and decision problems in depth. We'll formalize what makes a problem suitable for binary search on answer and develop the mathematical intuition that guarantees correctness.

Page Complete

You now understand the fundamental paradigm shift from searching for elements to searching for answers. This simple but profound insight unlocks a vast category of optimization problems that become tractable through binary search. Next, we'll deepen our understanding of why this technique works: the mathematics of monotonic functions and decision problems.

1 / 4

Loading learning content...

Data Structures & AlgorithmsBinary Search on Answer Space

Binary Search on Answer Space

LevelAdvanced

Duration90 mins

TopicBinary Search on Answer Space

1 / 4

When the Search Target Is an Answer, Not an Element

Beyond Array Lookups: A New Dimension of Binary Search

Consider this problem:

You have a conveyor belt carrying packages to be shipped within D days. Each package has a weight, and packages must be shipped in order. What is the minimum ship capacity needed to ship all packages within D days?

What You Will Learn

The Traditional Binary Search Mental Model

Before we extend binary search, let's crystallize what traditional binary search actually does. Understanding its essence reveals why the extension is natural.

Traditional binary search has three components:

Search Space: A sorted array containing potential answers
Target: A specific value you're looking for
Comparison Logic: Determines whether to go left or right

When you search for value x in array [1, 3, 5, 7, 9], you're asking: 'Where does x appear?' The array is explicit—every candidate is laid out before you.

traditional_binary_search.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def binary_search(arr: list[int], target: int) -> int:
    """
    Traditional binary search: find target in sorted array.
    Returns index if found, -1 otherwise.
    
    Search Space: arr[left..right]
    Target: specific value to find
    Logic: compare arr[mid] to target
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid  # Found it!
        elif arr[mid] < target:
            left = mid + 1  # Target is to the right
        else:
            right = mid - 1  # Target is to the left
    
    return -1  # Not found
 
# Example usage
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5))  # Output: 2 (index of 5)
print(binary_search(arr, 6))  # Output: -1 (not in array)

The Core Principle

The Paradigm Shift: From Elements to Answers

Now, let's make the conceptual leap. Instead of searching an array for an element, we search a range of values for an optimal answer.

The new mental model:

Traditional Binary Search	Binary Search on Answer Space
Search space: array elements	Search space: range of possible answers
Searching for: where target appears	Searching for: optimal feasible value
Comparison: `arr[mid] vs target`	Comparison: `canAchieve(mid)` (feasibility check)
Output: index of target	Output: the answer value itself

Traditional: Search for Element

•Array: [1, 3, 5, 7, 9]
•Target: 5
•Question: 'Is arr[mid] equal to 5?'
•Answer: The index where 5 lives
•Search space: explicitly stored

New: Search for Answer

•Range: [1, 1000000]
•Target: minimum feasible capacity
•Question: 'Can we ship with capacity mid?'
•Answer: The capacity value itself
•Search space: implicitly defined

Why 'Binary Search on Answer Space'?

The Implicit Search Space

Defining the implicit search space:

For any answer-space problem, you must determine:

Lower Bound (lo): The smallest possible answer
Upper Bound (hi): The largest possible answer

Ship Packages Problem — Defining BoundsGiven packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and D = 5 days, find minimum ship capacity.

Input

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], D = 5

Output

Minimum capacity = 15

Explanation

Lower bound: max(weights) = 10. (Ship must hold at least the heaviest package.) Upper bound: sum(weights) = 55. (Worst case: ship everything in 1 day.)

Search space: [10, 55] — 46 candidates instead of checking all possibilities.

With binary search: log₂(46) ≈ 6 checks instead of 46 linear checks.

Why bounds matter tremendously:

Choosing tight bounds is crucial for efficiency and correctness:

Too tight lower bound: You might miss the correct answer
Too loose upper bound: You waste search iterations
Just right: Minimal iterations, guaranteed correctness

For the shipping problem:

Lower bound max(weights) is necessary because the ship must fit the heaviest single package
Upper bound sum(weights) is sufficient because we could always ship everything in one day

This gives us a finite, bounded search space that binary search can efficiently explore.

defining_search_bounds.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def find_search_bounds_shipping(weights: list[int]) -> tuple[int, int]:
    """
    Determine the implicit search space for shipping problem.
    
    Lower bound: Must fit the heaviest package
    Upper bound: Ship everything at once (worst case)
    """
    lower_bound = max(weights)  # Can't be smaller than largest package
    upper_bound = sum(weights)  # Could ship all in 1 day
    
    return lower_bound, upper_bound
 
# Example
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
lo, hi = find_search_bounds_shipping(weights)
print(f"Search space: [{lo}, {hi}]")  # [10, 55]
print(f"Search space size: {hi - lo + 1}")  # 46 candidates
print(f"Binary search checks: ~{(hi - lo + 1).bit_length()}")  # ~6 checks

Bound Selection Is Problem-Specific

The Feasibility Predicate: The Heart of the Algorithm

The feasibility predicate is the function that replaces array comparison. Given a candidate answer mid, it returns:

True: This answer works (satisfies all constraints)
False: This answer doesn't work (violates at least one constraint)

This function is the most important piece of any answer-space binary search solution. Its correctness determines algorithm correctness; its efficiency determines overall time complexity.

Designing the feasibility predicate:

The predicate must answer a yes/no question: 'Can we achieve the goal with answer = mid?' For the shipping problem: 'Can we ship all packages in D days with capacity = mid?'

feasibility_predicate.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def can_ship_in_d_days(weights: list[int], D: int, capacity: int) -> bool:
    """
    Feasibility predicate for shipping problem.
    
    Question: Can we ship all packages in D days with given capacity?
    
    Strategy: Greedily load each day until capacity is reached.
    Count days needed; return True if days_needed <= D.
    
    Time Complexity: O(n) where n = len(weights)
    """
    days_needed = 1  # Start with day 1
    current_load = 0  # Current day's load
    
    for weight in weights:
        # If this package fits in current day's ship
        if current_load + weight <= capacity:
            current_load += weight
        else:
            # Start a new day
            days_needed += 1
            current_load = weight
            
            # Early termination: already exceeds D
            if days_needed > D:
                return False
    
    return days_needed <= D
 
# Example usage
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
D = 5
 
print(can_ship_in_d_days(weights, D, 10))  # False (needs 10 days)
print(can_ship_in_d_days(weights, D, 15))  # True (needs exactly 5 days)
print(can_ship_in_d_days(weights, D, 20))  # True (needs 4 days)
print(can_ship_in_d_days(weights, D, 55))  # True (needs 1 day)

Critical properties of the feasibility predicate:

Deterministic: Same input always gives same output
Efficient: Usually O(n) or O(n log n); otherwise binary search gains are lost
Monotonic with respect to the search space: This is essential for binary search to work

The monotonic property means:

If canAchieve(x) is True, then canAchieve(x+1) is also True (for minimization)
If canAchieve(x) is False, then canAchieve(x-1) is also False (for minimization)

This creates a clean boundary in the search space: all values below some threshold are infeasible; all values at or above are feasible.

Predicate Design Principle

Visualizing the Search Space Partition

Binary search on answer space works because the feasibility predicate partitions the search space into two contiguous regions:

[lo .................... X .................... hi]
 |←— INFEASIBLE —→|←——— FEASIBLE ———→|

For minimization problems (finding smallest feasible answer):

All values less than the optimal answer X are infeasible
All values ≥ X are feasible
We want to find X, the first feasible value

For maximization problems (finding largest feasible answer):

All values ≤ X are feasible
All values greater than X are infeasible
We want to find X, the last feasible value

Shipping Problem: Feasibility Across Answer Space
Capacity	Days Needed	Feasible (D=5)?	Region
10	10 days	❌ False	INFEASIBLE
11	9 days	❌ False	INFEASIBLE
12	8 days	❌ False	INFEASIBLE
13	6 days	❌ False	INFEASIBLE
14	6 days	❌ False	INFEASIBLE
15	5 days	✓ True	BOUNDARY (Answer)
16	5 days	✓ True	FEASIBLE
20	4 days	✓ True	FEASIBLE
30	3 days	✓ True	FEASIBLE
55	1 day	✓ True	FEASIBLE

Notice the clean partition: every capacity below 15 is infeasible, and every capacity at or above 15 is feasible. The answer is 15—the boundary point where feasibility changes.

Binary search finds this boundary efficiently by:

Checking the midpoint mid
If mid is feasible, the answer is at mid or to its left (for minimization)
If mid is infeasible, the answer is to the right of mid
Repeat until the boundary is found

This is exactly like finding the first True value in an array [False, False, False, False, False, True, True, True, ...].

The Partition Must Be Clean

The Complete Algorithm Template

Now let's assemble all the pieces into a complete algorithm. The template applies to virtually all 'binary search on answer' problems:

Algorithm structure:

Define search bounds: lo = minimum possible answer, hi = maximum possible answer
Define feasibility predicate: canAchieve(mid) returns True/False
Binary search to find the optimal boundary point
Return the answer

binary_search_on_answer_template.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def binary_search_on_answer(lo: int, hi: int, is_feasible) -> int:
    """
    Generic template for binary search on answer space.
    
    This finds the MINIMUM feasible value (for minimization problems).
    
    Args:
        lo: Lower bound of answer space
        hi: Upper bound of answer space  
        is_feasible: Predicate function (answer) -> bool
        
    Returns:
        The minimum value x such that is_feasible(x) == True
        
    Invariant: 
        - All values < answer are infeasible
        - All values >= answer are feasible
        
    Time Complexity: O(log(hi - lo) * cost_of_is_feasible)
    """
    answer = hi  # Default to upper bound (always feasible)
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if is_feasible(mid):
            # mid works! But maybe something smaller also works
            answer = mid  # Record this as best so far
            hi = mid - 1  # Search for smaller feasible value
        else:
            # mid doesn't work; need larger value
            lo = mid + 1
    
    return answer
 
 
def ship_within_days(weights: list[int], D: int) -> int:
    """
    Complete solution: Find minimum ship capacity to ship packages in D days.
    
    LeetCode 1011: Capacity To Ship Packages Within D Days
    """
    # Step 1: Define search bounds
    lo = max(weights)   # Must fit largest package
    hi = sum(weights)   # Could ship all at once
    
    # Step 2: Define feasibility predicate
    def can_ship(capacity: int) -> bool:
        days_needed = 1
        current_load = 0
        for weight in weights:
            if current_load + weight <= capacity:
                current_load += weight
            else:
                days_needed += 1
                current_load = weight
        return days_needed <= D
    
    # Step 3: Binary search for minimum feasible capacity
    return binary_search_on_answer(lo, hi, can_ship)
 
 
# Example usage
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
D = 5
print(f"Minimum capacity: {ship_within_days(weights, D)}")  # Output: 15

Complexity analysis:

Binary search iterations: O(log(hi - lo))
Each iteration: O(n) for the feasibility check
Total time: O(n × log(hi - lo))

For the shipping problem with weights summing to S:

Search space: O(S) values
Total time: O(n × log S)

This is dramatically better than brute force, which would try every capacity and take O(S × n) time.

Template Variations

For maximization problems, swap the logic: when feasible, search right (lo = mid + 1); when infeasible, search left (hi = mid - 1). The answer becomes the last feasible value rather than the first.

Recognizing Answer-Space Binary Search Problems

The key skill is recognizing when a problem can be solved with binary search on answer—even when the problem statement doesn't mention search at all. Here are the telltale signs:

Recognition Patterns

•Optimization language: 'Minimize the maximum X' or 'Maximize the minimum Y' — classic indicator of answer-space search
•Bounded answer range: The answer must lie within a finite, known range that you can determine from constraints
•Feasibility can be checked: Given a candidate answer, you can efficiently determine if it's achievable
•Monotonic feasibility: If answer X works, then X+1 definitely works (or vice versa for max problems)
•Keywords: 'minimum capacity', 'maximum distance', 'smallest time', 'largest possible', 'at most K', 'within D days'
•Constraint satisfaction: The problem asks for a value that satisfies multiple constraints simultaneously

The mental transformation:

Original problem:

'What is the minimum X such that [conditions are satisfied]?'

Transformed to binary search:

'For a given X, can [conditions be satisfied]? Binary search to find the smallest such X.'

This transformation turns an optimization problem into a decision problem. Binary search then efficiently explores the decision space.

Good Fit for Answer-Space Search

•Minimum ship capacity
•Maximum minimum distance between points
•Smallest largest sum when splitting array
•Minimum time to complete all tasks
•Maximum number of items with budget

NOT Suitable for This Technique

•Find all valid answers (not optimization)
•Non-monotonic feasibility
•Discrete choices without ordering
•Answer depends on path, not just value
•Feasibility check is exponential

The Reframing Trick

Common Mistakes and Pitfalls

Binary search on answer space is powerful but error-prone. Here are the most common mistakes and how to avoid them:

Pitfall Catalog

•Wrong bounds: Setting lo too high or hi too low causes missing the optimal answer. Always err on the side of wider bounds if unsure, then tighten based on problem analysis.
•Non-monotonic predicate: If your feasibility function isn't monotonic (flips between True/False multiple times), binary search will fail silently. Always verify monotonicity before implementing.
•Incorrect boundary logic: Confusing when to search left vs. right, or when to update the answer. Use the invariant: 'answer is the smallest (or largest) feasible value seen so far.'
•Off-by-one errors: The classic binary search bug. Ensure your loop condition (lo <= hi vs lo < hi) matches your update logic (mid + 1 vs mid).
•Inefficient feasibility check: If the predicate is O(n²) and search space is O(S), total time is O(n² log S)—possibly worse than brute force! Keep predicates efficient.
•Integer overflow in bounds: When searching large ranges (e.g., up to 10⁹), ensure lo + hi doesn't overflow. Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2.

common_bug_examples.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# ❌ WRONG: Bounds too tight - might miss answer
def bad_bounds(weights, D):
    lo = min(weights)  # Wrong! Must be >= max(weights)
    hi = sum(weights) // D  # Wrong! Might need more capacity
    # ... this fails for many inputs
 
# ❌ WRONG: Incorrect update logic
def bad_update_logic(lo, hi, is_feasible):
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_feasible(mid):
            lo = mid  # BUG: Never terminates! lo never moves up
        else:
            hi = mid - 1
    return lo
 
# ✓ CORRECT: Proper minimization template
def correct_minimization(lo, hi, is_feasible):
    answer = hi
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            answer = mid
            hi = mid - 1  # Try smaller
        else:
            lo = mid + 1  # Need larger
    return answer

Debug Strategy

Summary: The Answer-Space Paradigm

We've covered a major conceptual expansion of binary search. Let's consolidate the key ideas:

Key Takeaways

•Binary search works on any monotonic search space — not just arrays. The 'sortedness' of arrays is just one instance of monotonicity.
•Answer-space search has implicit search space — ranges like [min_possible, max_possible] rather than stored elements.
•The feasibility predicate is the core — a function that answers 'Is this candidate answer achievable?' The predicate must be efficient and monotonic.
•Feasibility partitions the search space — into infeasible (below boundary) and feasible (at/above boundary). We find the boundary.
•Recognition comes from problem structure — 'minimize maximum', 'find smallest X such that', bounded answers, and verifiable constraints all signal answer-space search.
•Complexity is O(log(range) × predicate_cost) — often O(n log S) where S is the answer-space size.

What's next:

Page Complete

1 / 4