讨论/《零起步学算法》 - 例题:搜索插入位置/
《零起步学算法》 - 例题:搜索插入位置

python

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1

        # 情况1 当数组为0或者目标小于第一个数则返回0
        if len(nums) == 0 or target < nums[0]:
            return 0
        
        # 情况2 当数组长度小于目标,则在数据尾部插入
        if nums[right] < target:
            return len(nums)
        
        # 情况3 当目标在数组区间内,[left, right] 查找插入元素的位置
        while left < right:
            # 中间值,向上取整的方式(右移)
            mid = left + (right - left) / 2
            if nums[mid] < target:
                # 下一轮搜索的区间是 [mid + 1, right]
                left =  mid + 1
            else:
                # 下一轮搜索的区间是 [left, mid]
                right = mid
        # left == right        
        return left
展开全部 7 讨论