def search_insert_position(nums, target):

    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2  
        
        if nums[mid] == target:
            return mid
       
        elif nums[mid] > target:
            right = mid - 1

        else:
            left = mid + 1
    
    return left

if __name__ == "__main__":
    
    nums1 = [1, 3, 5, 6] # = 2
    target1 = 5
    print(f"{search_insert_position(nums1, target1)}")

   
    nums2 = [1, 3, 5, 6] # = 1
    target2 = 2
    print(f"{search_insert_position(nums2, target2)}")

   
    nums3 = [1, 3, 5, 6] # =4
    target3 = 7
    print(f"{search_insert_position(nums3, target3)}")


    nums4 = [1, 3, 5, 6] # = 0
    target4 = 0
    print(f"{search_insert_position(nums4, target4)}")

    nums5 = []
    target5 = 1
    print(f"{search_insert_position(nums5, target5)}")