binary_insert.py

"""
# Binary Insert
"""
def binary_insert_right(arr, value, low=None, high=None):
    left  = 0          if low  is None else low
    right = len(arr)-1 if high is None else high - 1 # in bisect_right high is exclusive: [low, high)

    while left <= right:
        mid = (left + right)//2
        if arr[mid] <= value: # on duplicates, insert to the right side
            left = mid + 1
        else:
            right = mid - 1
    return left


if __name__ == '__main__':
    from utils import test
    test(binary_insert_right([1, 2, 2, 3, 5], 2), 3)
    test(binary_insert_right([1, 2, 2, 3, 5], 4), 4)
    test(binary_insert_right([1, 2, 2, 3, 5], 0), 0)
    test(binary_insert_right([1, 2, 2, 3, 5], 6), 5)
    test(binary_insert_right([], 1), 0)
    test(binary_insert_right([1], 1), 1)
    test(binary_insert_right([1], 0), 0)
    test(binary_insert_right([1, 1, 1, 1], 1), 4)
    test(binary_insert_right([2, 2, 2, 2], 1), 0)
    test(binary_insert_right(list(range(10)), 5), 6)
    test(binary_insert_right(list(range(0, 20, 2)), 7), 4)
    test(binary_insert_right([-5, -3, 0, 2, 4], -4), 1)
    test(binary_insert_right([-2, -1, 0, 1, 2], 1.5), 4)
    test(binary_insert_right([1.1, 2.2, 3.3], 2.0), 1)
    test(binary_insert_right([0.5, 1.5, 2.5], 1.7), 2)