Lower Bound Logic (First Valid Position)

Lower bound usually means: smallest index i such that predicate(i) is true, when predicate flips from false to true once. Binary search finds the first true.

Try this in Python

def lower_bound_first_true(n: int, predicate) -> int:
    """Assume: predicate False...False True...True. Return first True index in [0, n)."""
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def pred(i: int) -> bool:
    return i * i >= 50


print(lower_bound_first_true(20, pred))

Key takeaways

• Half-open [lo, hi) is common for lower bound templates.
• If predicate never becomes true, you may get n as answer—handle that in problems.
• Practice converting "minimize k such that ..." into a predicate.