class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            mid = (left + right) // 2
            print(mid, nums[mid])
            if nums[mid] == target: return mid
            elif nums[mid] < target:
                left = mid
            elif nums[mid] > target:
                right = mid
            if right - left == 1: 
                if target > nums[left]: return right
                else: return left
            print(left, right, mid)
        return 0