搜索插入位置

1、题目

图1

2、题解

二分法

• 先确定查找区间的左右开闭情况
  • 将区间定义左闭右开的好处：很多函数堆区间的操作都是左闭右开的形式；在返回值问题上，退出循环时，必然满足\(left==right\)，这样在最后返回值上就可以任意返回。
• 数组长度
  • 区间为左闭右开，数组长度就固定为\([0,len(nums))\)。
• 循环退出条件
  • 由于左闭右开，所以条件为\(left<right\)，不能有\(=\)。
• 中间值的写法
  • \(mid=left+(right-left)//2\)，这样写的目的是为了防止大数\((left+right)\)溢出。
• 中间值和目标值的比较关系
  • 当\(nums[mid]<target\)，表示得到比target校的数中的最大数时，left的值为\(mid+1\)，下一个值必然是大于等于target的值，此时可能取到和target相等的位置。
  • 当\(nums[mid]\leq target\)，当\(nums[mid]==target\)时，仍会进入条件，\(left=mid+1\)的值肯定是大于target的值，此时会收敛到第一个大于target的值。
• 左右区间变化
  • 区间变化取决于区间定义，所以\(left=mid+1,right=mid\)，right的真是取值为mid-1。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)

        while left < right:
            mid = (left + right)//2

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        
        return left