LeetCode【0035】搜索插入位置

本文目录

1 中文题目
2 求解方法：二分查找
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
3 题目总结

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

提示：

$\leq nums.length \leq 10^4$
$-10^4 \leq nums[i] \leq 10^4$
nums 为 无重复元素 的 升序 排列数组
- $10^4 \leq target\leq 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:# 特殊情况处理：如果数组为空，返回0if not nums:return 0left, 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