helper methods for implementing insertion sort given a sorted array and a target value return the index if the target is found if not return the index where it would be if it were inserted in order for example 1 3 5 6 5 2 1 3 5 6 2 1 1 3 5 6 7 4 1 3 5 6 0 0 given a sorted array and a target value return the index if the target is found if not return the index where it would be if it were inserted in order for example 1 3 5 6 5 2 1 3 5 6 2 1 1 3 5 6 7 4 1 3 5 6 0 0
def search_insert(array, val):
    
    low = 0
    high = len(array) - 1
    while low <=  high:
        mid = low + (high - low) // 2
        if val > array[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return low