LeetCode 35. 搜索插入位置

题目链接

35. 搜索插入位置

题目描述

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

三种解法对比分析

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

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

from typing import List

class 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 List

class 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 List

class 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 的位置。

三种解法对比分析

正确性验证（典型案例）

总结

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

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

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