Binary Search — Complete Guide: All Patterns & Problem Index

# Left boundary (first index where condition is True)
def binary_search(lo, hi):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid       # answer could be mid
        else:
            lo = mid + 1   # answer is after mid
    return lo  # lo == hi == first True position

# Right boundary (last index where condition is True)
def binary_search_right(lo, hi):
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # upper mid to avoid infinite loop
        if condition(mid):
            lo = mid       # answer could be mid
        else:
            hi = mid - 1   # answer is before mid
    return lo

def bs_on_answer(lo, hi):
    # lo = min possible answer, hi = max possible answer
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):  # can we achieve 'mid'?
            hi = mid       # try smaller (minimize)
        else:
            lo = mid + 1   # need larger
    return lo