搜索插入位置

标签: 数组 二分查找

难度: Easy

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

请必须使用时间复杂度为 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

示例 4:

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

示例 5:

输入: nums = [1], target = 0
输出: 0

提示:

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

注意：本题与主站 35 题相同： https://leetcode-cn.com/problems/search-insert-position/

Submission

运行时间: 21 ms

内存: 16.6 MB

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target > nums[-1]:
            return len(nums)
        elif target <= nums[0]:
            return 0

        head = 0
        tail = len(nums) - 1

        while head <= tail:
            middel = math.floor((head + tail)/2)
            if nums[middel] == target:
                return middel
            elif nums[middel] < target:
                if middel + 1 < len(nums):
                    if nums[middel + 1] >= target:
                        return middel + 1
                    else:
                        head = middel + 1
                else:
                    return middel + 1
            else:
                if middel - 1 >= 0:
                    if nums[middel - 1] > target:
                        tail = middel - 1
                    else:
                        if nums[middel - 1] == target:
                            return middel - 1
                        else:
                            return middel
                else:
                    return middel

Explain

这个题解通过使用二分查找来寻找目标值的位置，或者确定目标值应该插入的位置。算法首先检查目标值是否小于数组中的最小值或大于数组中的最大值，这两种情况下可以直接返回结果。然后使用两个指针，head 和 tail，初始化为数组的起始和结束位置，进行二分查找。当 head 不大于 tail 时，计算中间位置 middle，比较中间位置的元素与目标值。如果相等，则返回 middle 位置；如果目标值大于中间元素，则检查 middle 右侧的元素，调整 head；如果目标值小于中间元素，则检查 middle 左侧的元素，调整 tail。这样逐步缩小查找范围，直到找到目标值或确定其应该插入的位置。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target > nums[-1]:
            # 如果目标值大于数组中的最大值，则应插入到数组末尾
            return len(nums)
        elif target <= nums[0]:
            # 如果目标值小于等于数组中的最小值，则应插入到数组开头
            return 0

        head = 0
        tail = len(nums) - 1

        while head <= tail:
            middle = math.floor((head + tail) / 2)  # 计算中间位置
            if nums[middle] == target:
                # 找到目标值，返回对应的索引
                return middle
            elif nums[middle] < target:
                # 目标值大于中间值，调整查找范围到右半部分
                if middle + 1 < len(nums) and nums[middle + 1] >= target:
                    return middle + 1
                else:
                    head = middle + 1
            else:
                # 目标值小于中间值，调整查找范围到左半部分
                if middle - 1 >= 0 and nums[middle - 1] < target:
                    return middle
                elif middle - 1 >= 0 and nums[middle - 1] == target:
                    return middle - 1
                else:
                    tail = middle - 1

Explore

这个问题的核心在于理解二分查找的边界处理。算法中对`middle + 1`或`middle - 1`的检查主要是为了处理目标值`target`没有在数组中找到的情况，即确定`target`应该插入的位置。当`nums[middle]`不等于`target`时，如果`target`比`nums[middle]`大，检查`middle + 1`是为了确定`target`是否应该插入在`middle + 1`的位置；如果比`nums[middle]`小，则检查`middle - 1`是为了确定`target`是否应该插入在`middle`的位置。这些检查帮助算法精确地找到插入位置，尤其是当`target`位于数组中两个元素之间时。

是的，这种边界条件判断是必要的，它确保了插入位置的正确性。在二分查找过程中，当`target`大于`nums[middle]`且小于`nums[middle + 1]`时，`middle + 1`就是`target`应该插入的位置。类似地，当`target`小于`nums[middle]`且大于`nums[middle - 1]`时，`middle`是`target`应该插入的位置。这些条件判断帮助算法在数组中找到一个精确的插槽，以插入`target`，确保数组保持有序。

在二分查找中，无论数组长度是奇数还是偶数，`middle`的计算方式（`(head + tail) / 2`）都能有效地将查找范围分为两部分。如果数组长度是奇数，`middle`自然会是中间的元素；如果是偶数，`middle`将是中间两个元素中的左边一个。这种计算方式确保了每次迭代后查找区间都减半，不会漏掉任何元素。通过调整`head`和`tail`的值来相应地更新查找范围，可以确保算法总是能覆盖所有可能的查找区间。