Lower Bound — முதல் valid position

Lower bound: predicate(i) true ஆகும் சிறிய index — predicate false→true என மாறும் போது binary search முதல் 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

• [lo, hi) template அடிக்கடி பயன்படும்.
• Predicate எப்போதும் true ஆகாவிட்டால் விடை n வரலாம் — problem-இல் handle செய்யுங்கள்.
• "minimize k such that ..." → predicate ஆக மாற்றுவது practice.