问题说明（含示例）

问题描述：给定一个升序排序的数组 nums 和一个目标值 target，在数组中找到目标值并返回其索引。若目标值不存在于数组中，返回它按顺序插入的位置。要求算法的时间复杂度必须为 O(log n)。

示例：

1. 输入：nums = [1,3,5,6]，target = 5输出：2解释：目标值 5 存在于数组中，位于索引 2 处。

2. 输入：nums = [1,3,5,6]，target = 2输出：1解释：目标值 2 不存在于数组中，按升序应插入在 1 和 3 之间，对应索引 1。

3. 输入：nums = [1,3,5,6]，target = 7输出：4解释：目标值 7 大于数组中所有元素，应插入在数组末尾，对应索引 4（数组长度为 4）。

解题关键

由于数组是升序排序且要求 O(log n) 时间复杂度，最优解法是二分查找。核心思路是通过不断缩小搜索范围，定位目标值的位置或插入点：

1. 初始化指针：left = 0（左边界），right = len(nums) - 1（右边界）。
2. 二分循环：当 left <= right 时，计算中间索引 mid = (left + right) // 2，并比较 nums[mid] 与 target：
   • 若 nums[mid] == target：找到目标值，直接返回 mid；
   • 若 nums[mid] < target：目标值在右侧，更新 left = mid + 1；
   • 若 nums[mid] > target：目标值在左侧，更新 right = mid - 1。
3. 确定插入位置：当循环结束（left > right）时，left 即为目标值的插入位置（此时 left 是第一个大于 target 的元素索引，或数组长度）。

对应代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            # 计算中间索引（避免(left + right)溢出，等价于(left + right) // 2）
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid  # 找到目标值，返回索引
            elif nums[mid] < target:
                left = mid + 1  # 目标在右侧，移动左边界
            else:
                right = mid - 1  # 目标在左侧，移动右边界
        
        # 循环结束时，left即为插入位置
        return left

对应的基础知识

实现该算法需掌握以下基础概念与操作：

1. 二分查找的核心逻辑

   • 利用数组的有序性，通过比较中间元素与目标值，每次将搜索范围缩小一半（排除左半部分或右半部分），实现高效查找。
   • 循环条件 left <= right 确保所有可能的位置都被检查（包括 left == right 时的单个元素）。

2. 指针更新规则

   • 当 nums[mid] < target 时，目标值一定在 mid 右侧，故 left = mid + 1（跳过 mid 及左侧）；
   • 当 nums[mid] > target 时，目标值一定在 mid 左侧，故 right = mid - 1（跳过 mid 及右侧）。

3. 插入位置的确定

   • 循环结束时，left 必然大于 right，此时 left 的位置满足：所有 nums[0:left-1] < target 且 nums[left:end] > target（若 left 等于数组长度，则 target 大于所有元素），因此 left 是插入的正确位置。

4. 中间索引计算

   • 用 mid = left + (right - left) // 2 而非 (left + right) // 2，避免 left + right 数值过大导致的整数溢出（在 Python 中无溢出风险，但这是通用的安全写法）。

对应的进阶知识

该问题的解决涉及二分查找的深层逻辑与复杂度分析：

1. 时间复杂度分析

   • 每次循环将搜索范围从 n 缩小到 n/2，经过 log2(n) 次循环后范围缩小至 1，故时间复杂度为 O(log n)，满足题目要求。
   • 相比线性查找（O(n)），二分查找在大规模数组（如 n = 10^6）时效率提升显著（log2(10^6) ≈ 20 步）。

2. 二分查找的适用场景

   • 必须是有序数组（升序或降序，本题为升序）；
   • 支持随机访问（如数组，可通过索引直接访问中间元素；链表不适用，因访问中间元素需 O(n) 时间）。

3. 边界情况的隐性处理

   • 目标值小于所有元素（如 nums = [2,3,4]，target = 1）：循环结束后 left = 0，正确返回插入位置 0；
   • 目标值大于所有元素（如示例 3）：循环结束后 left = len(nums)，正确返回数组长度；
   • 数组为空（nums = []）：初始 right = -1，循环不执行，直接返回 left = 0，符合逻辑。

4. 与线性查找的对比

   • 线性查找（for i in range(len(nums)): ...）时间复杂度 O(n)，适用于小规模数组；
   • 二分查找 O(log n) 适用于大规模数组，是有序数组查找的最优策略，但需额外维护数组的有序性（插入 / 删除操作可能破坏有序性）。

编程思维与启示

1. “有序性” 的充分利用：面对有序数据，优先考虑二分查找而非暴力遍历，这是降低时间复杂度的关键（从 O(n) 到 O(log n)）。

2. “边界控制” 的精确性：二分查找的难点在于指针更新和循环终止条件的设计，left <= right 与 left = mid + 1/right = mid - 1 的配合，确保不遗漏任何可能位置，同时避免死循环。

3. “结果复用” 的巧思：循环结束后直接返回 left 而非额外计算插入位置，体现了对二分查找过程的深刻理解 —— 查找失败时的指针状态已隐含插入位置信息，无需冗余逻辑。

4. “通用写法” 的严谨性：中间索引用 left + (right - left) // 2 计算，虽在 Python 中无溢出问题，但这种写法适用于所有编程语言，体现了跨语言的代码通用性思维。