题目

1641440203(1).png

要点

  1. input： nums->list[int], target->int
  2. output: int, the (inserted) index of target
  3. O(logn) running time

代码

  1. class Solution:
  2.     def searchInsert(self, nums: List[int], target: int) -> int:
  3.         l=0
  4.         r=len(nums)-1
  6.         while(l<=r):
  7.             mid = (l+r)//2
  8.             if(target==nums[mid]):
  9.                 return mid
  10.             elif(nums[mid]<target):
  11.                 l=mid+1
  12.             else:
  13.                 r=mid-1
  14.         return l

分析

看到O(logn)就应当联想到用二分法，这道题的小细节在于除法用 // 可以保证mid取整数（因为mid = （l+r）/ 2 居然可能等于小数）。 其次考虑到为什么当查找不到时return l。

这里我们的思考方式是，在最坏情况下，因为mid是向下取整，且跳出循环的条件是l<=r。这里隐藏的条件是最后一次比较时，l=mid是一定的（此时要么l=mid=r,要么l=mid=r-1）。那么当targetnums[mid]时，应该插入到mid+1的位置，而在行10,11中，我们已经将l更新为mid+1了，所以插入位置=mid+1=l。

更多

在解题讨论中，有人提出，如果nums允许同一个数字出现多次，那么我们的代码要怎么变化呢？

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

        while(l<=r):
            mid = (l+r)//2

            if(target==nums[mid] and target!=nums[mid-1]):
                return mid
            elif(nums[mid]<target):
                l=mid+1
            else:
                r=mid-1

        return l

我们需要明白，这里的重复项特殊点在于target一定会被找到的时候，之前的答案会给出错误结果。
所以这里我们需要在line 9多检查一项： 找到数的前一项不等于target（因为如果等于的话，我们应该插入到前一个数的位置才对）。也就是说我们的else将包括以下情况1.target==nums[mid-1]; 2. nums[mid]>target。

之前我们陈述过，只要target能被找到，那么答案一定会在line10被返回，此时的条件为

  • l<=r
  • target已被找到
  • 前一个数不等于target

所以我们的算法是正确的。