Designing a monotone feasibility test

Understand the idea

A feasibility test answers one yes/no question cheaply. Prove that making the candidate larger cannot turn a feasible instance infeasible. Then design the test to preserve the problem's ordering and resource constraints.

Work through an example

The shipping test greedily fills each day in original order. A larger capacity can use the same grouping or merge groups, never requiring more days.

Time and space complexity

O(n) per shipping test; a search makes O(log S) tests.

Why it works

The current grouping uses no more days than any grouping of the same processed prefix at this capacity.

Common mistakes

• Reordering packages changes the problem.
• A nonmonotone success function cannot be binary-searched.

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