35_搜索插入位置

类型：数组

• 35. 搜索插入位置 💚

  https://leetcode-cn.com/problems/search-insert-position/

  ❓ 在已排序的数组（无重复元素）中找到目标值，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

  💡 二分查找

  我们需要找到这样一个位置 pos，使得：nums[pos−1] < target ≤ nums[pos]

  class Solution:
      def searchInsert(self, nums: List[int], target: int) -> int:
          if not nums:
              return 0
  
          low = 0
          high = len(nums) - 1
  
          while low <= high:
              mid = (low + high) // 2
              if nums[mid] == target:
                  return mid
              elif nums[mid] > target:
                  high = mid - 1
              else:
                  low = mid + 1
          return low

  时间复杂度：O(logN)，时间复杂度：O(1)