Python binary search: use a half-open interval and require sorted input

Operation contract

The search returns the first index whose receipt timestamp is at least the requested value. Its interval is half-open: left is included and right is excluded. Equal values move the right bound, so duplicates return their first insertion boundary rather than an arbitrary equal index. A request after every timestamp returns the sequence length.

Failure and ownership boundary

The function assumes ascending input. Sorting inside each query would add different work and alter caller ownership; rejecting or documenting unsorted input is a boundary decision. The fixture caps input length but does not spend a full linear scan verifying order on each call. Python lists: slicing copies the outer sequence, not nested objects and Java binary search: lower bounds and duplicate values share the same invariant.

Working program

def lower_bound(timestamps, target):
    if len(timestamps) > 10000:
        raise ValueError("sequence too large")
    left, right = 0, len(timestamps)
    while left < right:
        middle = (left + right) // 2
        if timestamps[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

print(lower_bound([10, 20, 20, 30], 20))
print(lower_bound([10, 20, 20, 30], 40))
print(lower_bound([], 20))

Output

1
4
0

Costs and limits

For n already sorted bounded integer values, the search uses O(log n) comparisons and O(1) working slots. Sorting, validating order and arbitrary-size integer costs are outside that comparison count.

Common Mistakes

• Keep the interval convention consistent.
• The logarithmic search assumes sorted input.

Connected lessons

Python lists: slicing copies the outer sequence, not nested objects, Python syntax reference: inspect shape, unpacking and mutation rules, Java binary search: lower bounds and duplicate values.

Follow the integrity boundary

Python binary search on capacity: prove the feasibility predicate.