LeetCode 35 搜索插入位置题解

LeetCode 35 搜索插入位置题解

题目描述

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

解题思路

二分查找法

1. 区间定义：采用左闭右闭区间 [left, right]
2. 循环条件：left <= right 保证区间有效性
3. 指针移动：
   • 中间值 < 目标值 → 搜索右半区（left = mid + 1）
   • 中间值 > 目标值 → 搜索左半区（right = mid - 1）
4. 终止条件：当 left > right 时，left 即为插入位置
   循环终止条件 当 left > right 时循环终止，此时：

• left 指向第一个 大于 目标值的元素位置
• right 指向最后一个 小于 目标值的元素位置

初始区间 [0,3] → mid=1（值为3）
3 > 2 → 右指针移动：right=0
新区间 [0,0] → mid=0（值为1）
1 < 2 → 左指针移动：left=1
循环终止，left=1 → 正确插入位置

关键点解析

# 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
# 请必须使用时间复杂度为 O(log n) 的算法。
# 示例 1:
# 输入: nums = [1,3,5,6], target = 5
# 输出: 2
# 示例 2:
# 输入: nums = [1,3,5,6], target = 2
# 输出: 1
from typing import List

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2  # 中间索引计算
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:   # 目标在右侧
                left = mid + 1         # 收缩左边界
            else:                       # 目标在左侧
                right = mid - 1        # 收缩右边界
        return left  # 插入位置为最终left值

if __name__ == "__main__":
    test1 = Solution().searchInsert([1,3,5,6], 5)  # 2
    test2 = Solution().searchInsert([1,3,5,6], 2)   # 1
    print(test1, test2)

3 # 插入到数组最后面

复杂度分析

算法优势

1. 严格对数复杂度：每次循环排除一半元素
2. 内存效率高：仅使用常数额外空间
3. 代码简洁：无需处理复杂边界条件