Pattern1 Practice3 Interview

Binary Search on Answer

GuideCode Labs

Binary-search a monotone feasibility predicate when the answer lies in an ordered numeric space. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Binary Search on Answer when the prompt's constraints and required operations match this shape: Binary-search a monotone feasibility predicate when the answer lies in an ordered numeric space.

On this page · Search a Feasible Answer Space

Checking your account…

Search a Feasible Answer Space

Sometimes the result is a number rather than an input position. Establish lower and upper bounds that contain every possible answer, then binary-search that numeric domain.

Build a Monotone Feasibility Test

A predicate must switch only once: for a minimization problem, capacities below the answer fail and capacities at or above it succeed. Test extreme candidates before trusting the search.

Build a Capacity Feasibility Table

Reference

def capacity_table(weights,days,candidates):
    def feasible(capacity):
        used=1; load=0
        for weight in weights:
            if weight>capacity: return False
            if load+weight>capacity: used+=1; load=0
            load+=weight
        return used<=days
    return [feasible(value) for value in candidates]

Practice

Implement capacity_table(weights,days,candidates). Return whether each candidate capacity ships the ordered weights within days.

def capacity_table(weights,days,candidates):
    pass

Public tests

Expose a monotone predicate

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Keep the Best Feasible Boundary

Use a first-true template. A feasible midpoint remains a candidate, so move right to mid; an infeasible midpoint can be discarded with everything below it, so move left to mid plus one.

Find Minimum Feasible Capacity

Reference

def minimum_capacity(weights,days):
    left,right=max(weights),sum(weights)
    def feasible(capacity):
        used=1; load=0
        for weight in weights:
            if load+weight>capacity: used+=1; load=0
            load+=weight
        return used<=days
    while left<right:
        mid=(left+right)//2
        if feasible(mid): right=mid
        else: left=mid+1
    return left

Practice

Implement minimum_capacity(weights,days). Return the smallest capacity that ships ordered weights within days.

def minimum_capacity(weights,days):
    pass

Public tests

Keep the feasible boundary

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Answer Search or Direct Construction

Use answer search when feasibility is cheaper than constructing the optimum and the answer domain is ordered. Prefer direct greedy or dynamic programming when it already yields the exact value in comparable time. Total cost is predicate cost times logarithm of the answer range.

Explain It in an Interview

Say: “Feasibility is monotone because increasing capacity cannot require more days. My bounds are max item and total sum, and I keep the first feasible boundary.” Distinguish binary searching input indexes from searching possible answers.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Binary Search on Answer invariant is independent of a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Binary Search on Answer decision loop	`O(log n)`	`O(log n)`	When feasibility changes monotonically as a numeric answer grows, search the answer range instead of enumerating candidates. left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right].

Space

O(1) for the focused Minimize a Feasible Value implementation.

Assumptions

Feasibility is monotone in the square side length. A feasible midpoint keeps the answer at or below mid; an infeasible midpoint proves every smaller candidate impossible, so convergence returns the minimum feasible side.
The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

State the precise Binary Search on Answer invariant before coding and preserve it after every update, traversal step, or recursive return.
The answer remains inside the current inclusive or half-open bounds.
Feasibility changes direction at most once.
When feasibility changes monotonically as a numeric answer grows, search the answer range instead of enumerating candidates. Preserve this property after every transition.
left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right]. Preserve this property after every transition.

When To Use Or Avoid Binary Search on Answer

Use It When

Use Binary Search on Answer when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
Use it when the answer remains inside the current inclusive or half-open bounds.

Choose Another Tool When

Avoid Binary Search on Answer when its decision rule cannot eliminate work or preserve the required state.
Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Minimize a Feasible Value before optimizing.

Avoid

def minimum_square_side(item_count):
    pass

Use instead

def minimum_square_side(item_count):
    left, right = 0, item_count
    while left < right:
        mid = (left + right) // 2
        if mid * mid >= item_count:
            right = mid
        else:
            left = mid + 1
    return left

Where you will hit this: Minimize a Feasible Value(opens in a new tab)

Breaking the maintained state

Uses a strict feasibility comparison and overshoots whenever the item count is a perfect square.

Prevent it: Use the public tests and preserve this state: The answer remains inside the current inclusive or half-open bounds.

Avoid

def minimum_square_side(item_count):
    left, right = 0, item_count
    while left < right:
        mid = (left + right) // 2
        if mid * mid > item_count:
            right = mid
        else:
            left = mid + 1
    return left

Use instead

def minimum_square_side(item_count):
    left, right = 0, item_count
    while left < right:
        mid = (left + right) // 2
        if mid * mid >= item_count:
            right = mid
        else:
            left = mid + 1
    return left

Where you will hit this: Minimize a Feasible Value(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(log n).

Avoid

def minimum_square_side(item_count):
    left, right = 0, item_count
    while left < right:
        mid = (left + right) // 2
        if mid * mid > item_count:
            right = mid
        else:
            left = mid + 1
    return left

Use instead

def minimum_square_side(item_count):
    left, right = 0, item_count
    while left < right:
        mid = (left + right) // 2
        if mid * mid >= item_count:
            right = mid
        else:
            left = mid + 1
    return left

Where you will hit this: Cutting Ribbons(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python bisect — Array Bisection Algorithm(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…