DSA Lower Bound

How it works

Use the same half-open interval discipline as binary search, but keep a different invariant: values before left are strictly smaller, while values at or beyond right cannot be earlier valid answers. Equality moves right toward the first matching position rather than returning immediately. The result can equal len(values), which is a valid insertion point but not an existing element index.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as lower-bound.py and run python lower-bound.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def lower_bound(values, target):
    left, right = 0, len(values)
    while left < right:
        middle = (left + right) // 2
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

print(lower_bound([2, 5, 5, 11, 14], 5))
print(lower_bound([2, 5, 5, 11, 14], 99))
print(lower_bound([], 3))

Expected result

1
5
0

The first five belongs at position one, an oversized target belongs after all five items, and an empty sequence accepts insertion at zero. Check the returned position against the sequence length before indexing to confirm membership.

Time, space and assumptions

On a sorted random-access sequence, this method uses O(log n) comparisons and O(1) workspace. Inserting into a Python list at that position can still require O(n) shifts.