35.搜索插入位置

对于target在nums中插入的位置，只有四种情况

1. target比nums中所有元素都小
2. target比nums中所有元素都大
3. target在nums中出现过
4. target在nums中没有出现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target <= nums[0]: # target比nums中所有元素都小，插到第一位
            return 0
        if target > nums[-1]: # target比nums中所有元素都大，插到最后一位
            return len(nums)
        i, j = 0, len(nums) - 1 # 在nums中出现，二分查找
        while j > i+1:
            k = (i +j) // 2
            if nums[k] >= target:
                j = k
            else:
                i = k
        return j

评论