Binary search over an answer

Understand the idea

Binary search can find a smallest feasible answer rather than an array element. Build a domain with infeasible values before feasible ones, choose valid bounds, and keep a feasible upper bound.

Work through an example

Shipping weights [3,2,2,4,1,4] in three days has capacity bounds 4..16. Capacity 5 needs four days; capacity 6 needs three, so the minimum is 6.

Time and space complexity

O(n log S) for n weights and capacity-range width S; O(1) auxiliary state.

Why it works

The optimum stays in [lo,hi]; hi is feasible, and values below lo are impossible.

Common mistakes

• Bounds must include every possible optimum.
• Search requires a truly monotone feasibility predicate.

Chapter lab · Python implementation

Binary search discards half a monotone candidate domain. The lab uses half-open [lo,hi) lower-bound search. Write the invariant and update rules together; mixing inclusive and half-open conventions creates off-by-one bugs. A logarithmic search does not make list insertion logarithmic.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def lower_bound(values,target):
    lo,hi=0,len(values)
    while lo<hi:
        mid=lo+(hi-lo)//2
        if values[mid]<target:
            lo=mid+1
        else:
            hi=mid
    return lo

def exact(values,target):
    i=lower_bound(values,target)
    return i if i<len(values) and values[i]==target else -1

def minimum_capacity(weights,days):
    if days<1 or not weights or any(w<1 for w in weights):
        raise ValueError('positive weights and days required')
    def feasible(capacity):
        used,load=1,0
        for w in weights:
            if load+w>capacity:
                used+=1; load=0
            load+=w
        return used<=days
    lo,hi=max(weights),sum(weights)
    while lo<hi:
        mid=(lo+hi)//2
        if feasible(mid): hi=mid
        else: lo=mid+1
    return lo

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert lower_bound([1,3,3,7],3)==1
assert lower_bound([],5)==0
assert exact([1,3,3,7],4)==-1
assert exact([1,3,3,7],7)==3
assert minimum_capacity([3,2,2,4,1,4],3)==6