Lower and upper bounds

Understand the idea

Lower bound finds the first value≥target; upper bound finds the first value>target. Their difference counts occurrences and their positions define a half-open equal-value range. Equal-range boundaries also handle targets before the first element or beyond the last: both return zero or n. Test all-equal input to ensure the loop still narrows and returns the correct endpoints.

Work through an example

In [1,3,3,3,7], lower(3)=1 and upper(3)=4; count=3. For a missing value, both boundaries coincide.

Time and space complexity

Two searches O(log n); inserting into a packed list remains O(n).

Why it works

Before upper's lo values≤target; from hi onward values>target.

Common mistakes

• Changing < to <= changes the boundary meaning.
• bisect requires sorted input.

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