class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:

        if target in nums: #如果target存在于nums中

            return nums.index(target)

        elif target < nums[0]: #如果target比数组第一个元素小

            return 0

        elif target > nums[-1]: #如果target比数组最后一个元素大

            return len(nums)

        else:

            for i in range(len(nums)-1):

                if nums[i] < target and nums[i+1] > target:

                    return i+1

class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:

        size=len(nums)

        #特判1

        if size==0:

            return 0

        #特判2：如果target大于最后一个元素

        if nums[-1]<target:

            return size

        left=0

        right=size-1

        #二分法逻辑判断

        while left<right:

            mid=left+(right-left)//2 #mid=(left+right)//2 但是(left+right)可能会整型溢出，故换一种写法

            if nums[mid]<target:

                left=mid+1

            else:

                assert nums[mid] >= target

                right=mid

        return left