Reference Implementations

def find_insert_point(values, target):
    """
    Locate where target belongs in a sorted list via binary search.

    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    if not values:
        return 0

    # Narrow the window until it is empty
    low, high = 0, len(values)

    while low < high:
        mid = (low + high) // 2
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid

    return low

# Test cases
print(find_insert_point([2, 5, 9, 14], 9))       # 2
print(find_insert_point([], 3))                    # 0