LeetCode【0035】搜索插入位置

1 中文题目

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

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

示例：

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

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

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

提示：

• $1\le nums.length\le 10^4$
• $-10^4\le nums[i]\le 10^4$
• nums 为 无重复元素 的 升序 排列数组
• -$10^4\le target\le 10^4$

---

2 求解方法：二分查找

2.1 方法思路

方法核心

• 使用二分查找定位目标值或插入位置
• 处理特殊边界情况
• 利用二分查找的特性确定插入位置

实现步骤

（1）前置处理：

• 检查数组是否为空，如果为空直接返回0
• 检查目标值是否小于数组第一个元素，如果是则返回0
• 检查目标值是否大于数组最后一个元素，如果是则返回数组长度

（2）二分查找过程：

• 初始化左右指针，分别指向数组的开始和结束
• 进入循环，当左右指针未交叉时继续
• 计算中间位置，注意使用防止整数溢出的写法
• 比较中间元素与目标值的大小关系
• 根据比较结果调整左右指针的位置
• 如果找到目标值，直接返回位置
• 如果未找到，继续缩小查找范围

（3）结果处理：

• 如果循环结束仍未找到目标值，此时left指针的位置就是目标值应该插入的位置，返回left指针的位置

方法示例

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

详细执行过程：

1. 初始检查：
   - 数组不为空，继续处理
   - target = 2 > nums[0] = 1，继续处理
   - target = 2 < nums[-1] = 6，继续处理

2. 二分查找过程：
   第一次迭代：
   - left = 0, right = 3
   - mid = 1
   - nums[mid] = 3 > target = 2
   - right = mid - 1 = 0

   第二次迭代：
   - left = 0, right = 0
   - mid = 0
   - nums[mid] = 1 < target = 2
   - left = mid + 1 = 1

   循环结束：
   - left = 1，right = 0
   - 返回 left = 1

解释：
- 2应该插入到索引1的位置
- 即插入到1和3之间

2.2 Python代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 特殊情况处理：如果数组为空，返回0
        if not nums:
            return 0
            
        left, right = 0, len(nums) - 1
        
        # 特殊情况处理：如果目标值小于数组第一个元素
        if target < nums[0]:
            return 0
        # 特殊情况处理：如果目标值大于数组最后一个元素
        if target > nums[-1]:
            return len(nums)
            
        # 二分查找
        while left <= right:
            # 计算中间位置，防止溢出
            mid = left + (right - left) // 2
            
            # 如果找到目标值，直接返回
            if nums[mid] == target:
                return mid
            # 如果中间值大于目标值，在左半部分继续查找
            elif nums[mid] > target:
                right = mid - 1
            # 如果中间值小于目标值，在右半部分继续查找
            else:
                left = mid + 1
                
        # 如果没找到目标值，返回应该插入的位置
        return left

2.3 复杂度分析

• 时间复杂度：O(log n)
  • 使用二分查找算法
  • 每次迭代将搜索范围减半
• 空间复杂度：O(1)
  • 只使用常数额外空间

---

3 题目总结

题目难度：简单
数据结构：数组
应用算法：二分查找

原文地址：https://blog.csdn.net/qq_32882309/article/details/143740566

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！