搜索插入位置

🎯 问题描述（来源于LeetCode）

描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。
说明：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • -104 <= target <= 104

示例：

  • 示例 1：
1
2
输入: nums = [1,3,5,6], target = 5
输出: 2
  • 示例 2：
1
2
输入: nums = [1,3,5,6], target = 2
输出: 1

💻 解题思路

思路1：二分查找

思路1：代码实现

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

思路1：📊 性能分析

提交结果
  • 运行时间：0ms击败100.00%
  • 内存消耗：19.72MB击败37.28%
复杂度验证
  • 时间复杂度：O(logn)O(log n)
  • 空间复杂度：O(1)O(1)

思考