搜索插入位置

标签: 数组 二分查找

难度: Easy

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

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

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

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

Submission

运行时间: 32 ms

内存: 15.4 MB

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

Explain

这个题解使用了二分查找的思路。首先定义左右边界 l 和 r,分别指向数组的开始和结束位置。然后使用 while 循环进行二分查找,每次循环都计算中点 mid,比较 nums[mid] 和 target 的大小关系。如果 nums[mid] >= target,说明目标值可能在左半部分,将右边界 r 移动到 mid;否则目标值在右半部分,将左边界 l 移动到 mid + 1。最终左右边界重合时,l 即为目标值应该插入的位置。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0  # 左边界指针
        r = len(nums)  # 右边界指针
        while l < r:
            mid = l + (r - l) // 2  # 计算中点位置
            if nums[mid] >= target:  # 如果中点值大于等于目标值
                r = mid  # 将右边界移动到中点
            else:  # 否则
                l = mid + 1  # 将左边界移动到中点右侧
        return l  # 返回目标值应该插入的位置

Explore

在二分查找中,将r移动到mid而不是mid-1是为了确保不错过目标值target。如果nums[mid]等于target,那么mid就是一个可能的插入位置。将r设为mid而不是mid-1,可以保持搜索范围内仍包含当前找到的target的位置,从而确保能找到最左边的插入点。如果将r设为mid-1,则可能会错过正确的插入位置,尤其是当数组中存在多个相同的元素时。这种选择在效率上可能会导致额外的几次迭代,但在结果上更能确保正确性。

使用l < r作为循环条件的主要原因是避免在搜索空间为空时还执行循环体。在l等于r时,搜索空间为空,因此没有必要再继续检查。这样设计可以防止无限循环和访问数组越界。同时,因为算法在每次迭代时都精确调整l或r,所以当l等于r时,l指向的位置就是target应该插入的位置,从而确保不会错过目标值。

二分查找算法计算中点位置时使用的是mid = l + (r - l) / 2公式,这种方式可以防止在计算mid时可能发生的整数溢出(如果直接使用(l + r) / 2可能会溢出)。因此,即使数组中的元素值非常大或接近整型的极限值,只要不超过整型的表示范围,这种计算方法仍然有效,不会影响算法的正确性。

在二分查找中,每次迭代都是在缩小搜索范围,直到l与r重合。此时,l(或r)指向的位置正是target可以插入的正确位置。这是因为每次循环都是根据nums[mid]与target的比较来调整l或r,确保不会错过target应该存在的位置。当l与r重合时,这个位置就是最终确定的插入位置,无论target是否存在于数组中。