Binary Search Templates

binary_search.py

# https://leetcode.com/discuss/post/2371234/an-opinionated-guide-to-binary-search-co-1yfw/
def minimization(arr, condition):
    """
    Find the first time a condition is True.
    [F, F, F, (T), T, T, T]
    (T) is the first time the conditions is True.
    r is the True answer (always T)
    l is always invalid (always F)
    """
    l, r = -1, len(arr) - 1 # if len(arr) is a candidate
    while l + 1 < r:
        p = (l + r) // 2
        if condition(p):
            r = p
        else:
            l = p
    return r

def maximization(arr, condition):
    """
    Find the first time a condition is False
    [T, T, T, T, (F), F, F]
    (F) is the first time the condition is False.
    l is the True answer (always T)
    r is invalid (always F)
    """
    l, r = -1, len(arr) # l = 0 if -1 is not a candidate
    while l + 1 < r:
        p = (l + r) // 2
        if condition(p):
            l = p
        else:
            r = p
    return l