35. 搜索插入位置

题目链接：35. 搜索插入位置

题目描述

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

核心思考：二分查找寻找首个大于等于目标的值

这是一道标准的**二分查找（Binary Search）**寻找插入位置或者“下界”的经典题型。核心在于定义好左右边界的闭合区间与收缩策略。

• 初始化：left = 0，right = len(nums) - 1，我们在闭区间 [left, right] 内寻找。
• 折半匹配：计算出中点索引 mid 后：
  1. 如果 nums[mid] == target，命中了目标，直接返回当前的 mid 下标。
  2. 如果 nums[mid] < target，说明目标值还在右方，下一轮搜索区间整体收缩为右半部：left = mid + 1。
  3. 如果 nums[mid] > target，说明目标值必定在左方，下一轮搜索区间收缩为左半部：right = mid - 1。
• 循环结束与返回值：如果一直到 left > right 循环退出时还没找到目标，此时的 left 指针实际上刚好指向了第一个大于 target 的元素下标位置。这恰巧就是符合升序排列预期的最佳插入点所在！

解题思路 (Python)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 不在的时候就是返回第一个大于他的index 靠右
        left = 0
        right = len(nums)-1
        while left <= right:
            mid = left + (right-left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                return mid
        return left

复杂度分析

• 时间复杂度：O(log N)，N 表示数组的长度。采用对半折叠持续削减寻找区间，这是二分算法的固有对数复杂度。
• 空间复杂度：O(1)，代码仅利用了左右游标变量标尺，没有任何空间开支。