二分查找

方法一二分查找

题目要求使用O(logn)的时间复杂度，因此不能使用排序。如果没找到。插入位置就是最后low的位置

参考代码

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

复杂度分析

时间复杂度 O(logn)
空间复杂度 O(1)

当然可以直接使用库函数,这里要注意不能使用bisect而要使用bisect_left。bisect会返回最右边的插入位置，bisect_left会返回最左边的。当数据不存在的情况两者皆可，但数据存在题目要求的是返回target的位置，并不是插入进去，bisect_left就等价于题目要求的输出

  1. class Solution:
  2.     def searchInsert(self, nums: List[int], target: int) -> int:
  3.         return bisect.bisect_left(nums,target)