LeetCode 35. 搜索插入位置

题目链接

35. 搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。要求算法时间复杂度为 O(log n)。

三种解法对比分析

三种解法均基于二分查找，核心目标是找到“第一个大于等于目标值的位置”（即目标值的插入位置）。差异体现在二分查找的循环条件和边界处理上。

解法一：循环条件 left <= right（经典二分）

from typing import Listclass Solution: def searchInsert(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 # 初始右边界为数组最后一个元素的索引 while left <= right: # 当left > right时退出循环 m = (left + right) // 2 # 中间位置 if nums[m] >= target: # 中间值 >= 目标值，收缩右边界（寻找更左的位置） right = m - 1 else: # 中间值 < 目标值，收缩左边界 left = m + 1 # 循环结束后，left即为第一个 >= target的位置（插入位置） return left

核心特点

1. 循环条件：left <= right，这是最经典的二分查找循环条件，当 left > right 时退出循环。
2. 边界设置：
   • 左边界 left = 0（数组起始索引）。
   • 右边界 right = len(nums) - 1（数组最后一个元素的索引）。
3. 收缩逻辑：
   • 若 nums[m] >= target：目标值可能在左侧，右边界收缩至 m - 1（跳过当前 m，后续通过 left 还原）。
   • 若 nums[m] < target：目标值必在右侧，左边界收缩至 m + 1（跳过当前 m）。
4. 返回值：left，此时 left > right，且 left 是第一个满足 nums[left] >= target 的位置（若目标值不存在，即为插入位置）。

解法二：循环条件 left < right

from typing import Listclass Solution: def searchInsert(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) # 初始右边界为数组长度（而非最后一个索引） while left < right: # 当left == right时退出循环 m = (left + right) // 2 # 中间位置 if nums[m] >= target: # 中间值 >= 目标值，收缩右边界（保留m作为候选） right = m else: # 中间值 < 目标值，收缩左边界 left = m + 1 # 循环结束后，left == right，即为插入位置 return left

核心特点

1. 循环条件：left < right，当 left == right 时退出循环，避免死循环。
2. 边界设置：
   • 左边界 left = 0。
   • 右边界 right = len(nums)（数组长度，覆盖“目标值大于所有元素”的情况）。
3. 收缩逻辑：
   • 若 nums[m] >= target：右边界收缩至 m（保留 m 作为候选，因为可能是第一个 >= 目标值的位置）。
   • 若 nums[m] < target：左边界收缩至 m + 1（m 不可能是目标位置，直接跳过）。
4. 返回值：left（此时 left == right），直接对应目标值的插入位置。

解法三：循环条件 left + 1 < right（开区间处理）

from typing import Listclass Solution: def searchInsert(self, nums: List[int], target: int) -> int: left = -1 # 左边界初始化为-1（超出数组范围） right = len(nums) # 右边界初始化为数组长度 while left + 1 < right: # 当left和right相邻时退出循环 m = (left + right) // 2 # 中间位置 if nums[m] >= target: # 中间值 >= 目标值，收缩右边界 right = m else: # 中间值 < 目标值，收缩左边界 left = m # 循环结束后，right即为插入位置 return right

核心特点

1. 循环条件：left + 1 < right（左右边界不相邻），当 left 和 right 相邻时退出循环。
2. 边界设置：
   • 左边界 left = -1（超出数组左边界，确保覆盖所有可能的左侧位置）。
   • 右边界 right = len(nums)（覆盖所有可能的右侧位置）。
3. 收缩逻辑：
   • 若 nums[m] >= target：右边界收缩至 m（不跳过 m，因为可能是目标位置）。
   • 若 nums[m] < target：左边界收缩至 m（不跳过 m，循环条件保证最终收敛）。
4. 返回值：right，此时 left 和 right 相邻，right 是第一个满足 nums[right] >= target 的位置。

三种解法对比分析

维度 解法一（left <= right） 解法二（left < right） 解法三（left + 1 < right） 循环条件 left <= right（left > right 退出） left < right（left == right 退出） left + 1 < right（相邻时退出） 初始边界 left=0, right=len(nums)-1 left=0, right=len(nums) left=-1, right=len(nums) 收缩逻辑 跳过 m（left/right = m ± 1） 保留 m（right = m） 不跳过 m（left/right = m） 返回值 left left（left == right） right 越界处理 天然支持（left 可等于 len(nums)） 天然支持（right 初始为 len(nums)） 天然支持（范围覆盖所有可能） 直观性 高（经典二分逻辑） 中等（右边界非索引） 较高（开区间包围目标） 适用场景 入门教学、简单二分场景 工程实现、大多数二分场景 复杂边界场景

正确性验证（典型案例）

测试用例 解法一 解法二 解法三 预期结果 nums = [1,3,5,6], target = 5 2 2 2 2 nums = [1,3,5,6], target = 2 1 1 1 1 nums = [1,3,5,6], target = 7 4 4 4 4 nums = [1,3,5,6], target = 0 0 0 0 0 nums = [], target = 0 0 0 0 0

总结

三种解法均通过二分查找实现 O(log n) 时间复杂度，核心目标是找到“第一个大于等于目标值的位置”，即插入位置。差异主要在于边界处理和循环条件：

• 解法一：经典二分查找逻辑，循环条件 left <= right，适合入门理解，需注意循环结束后 left 的含义。
• 解法二：通过 left < right 简化循环条件，右边界初始为 len(nums)，天然支持越界情况，工程中常用。
• 解法三：开区间处理方式，边界范围覆盖所有可能位置，逻辑严谨，适合复杂边界场景。

三种方法均能正确解决问题，选择取决于个人对二分查找边界的理解习惯。核心是理解“插入位置”的本质——数组中第一个大于等于目标值的位置，这也是二分查找“下界”的典型应用。