Exact search

Understand the idea

Exact search can use lower bound then verify equality. Finding an insertion position alone does not prove the target exists. Check the boundary against n before indexing.

Work through an example

For target 4 in [1,3,3,7], lower bound returns 3, but value 7 differs, so exact returns -1. For target 8 it returns n and must not index.

Time and space complexity

O(log n) time/O(1) state; duplicates return the first occurrence here.

Why it works

The first possible equal element is at the lower-bound boundary.

Common mistakes

• A returned boundary may equal n.
• The chosen duplicate occurrence should be documented.

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