def METHOD_NAME(ls, v):
    """Take a list ls and a value v such that ls is sorted and v is comparable
    with the elements of ls.
    Return an index i such that 0 <= i <= len(v) with the properties:
    1. ls.insert(i, v) is sorted
    2. ls.insert(j, v) is not sorted for j < i
    """
    # Without this check we will get an index error on the next line when the
    # list is empty.
    if not ls:
        return 0
    # Without this check we will miss the case where the insertion point should
    # be zero: The invariant we maintain in the next section is that lo is
    # always strictly lower than the insertion point.
    if v <= ls[0]:
        return 0
    # Invariant: There is no insertion point i with i <= lo
    lo = 0
    # Invariant: There is an insertion point i with i <= hi
    hi = len(ls)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if v > ls[mid]:
            # Inserting v anywhere below mid would result in an unsorted list
            # because it's > the value at mid. Therefore mid is a valid new lo
            lo = mid
        # Uncommenting the following lines will cause this to return a valid
        # insertion point which is not always minimal.
        # elif v == ls[mid]:
        #   return mid
        else:
            # Either v == ls[mid] in which case mid is a valid insertion point
            # or v < ls[mid], in which case all valid insertion points must be
            # < hi. Either way, mid is a valid new hi.
            hi = mid
    assert lo + 1 == hi
    # We now know that there is a valid insertion point <= hi and there is no
    # valid insertion point < hi because hi - 1 is lo. Therefore hi is the
    # answer we were seeking
    return hi