搜索插入位置：二分查找的巧妙应用

问题描述

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

示例：

• 示例1：

  输入: nums = [1,3,5,6], target = 5
  输出: 2

• 示例2：

  输入: nums = [1,3,5,6], target = 2
  输出: 1

• 示例3：

  输入: nums = [1,3,5,6], target = 7
  输出: 4

解题思路

为什么用二分查找？

由于数组已排序，且要求时间复杂度为 O(log n)，自然联想到二分查找。但不同于标准二分查找的是，当目标值不存在时，需要找到插入的位置。

核心思路

1. 初始化指针：定义两个指针 left 和 right，分别指向数组的首尾。

2. 二分缩小范围：

   • 计算中间索引 mid。

   • 比较 nums[mid] 与 target：

     • 若 nums[mid] < target，说明目标值在右半部分，调整 left = mid + 1。

     • 否则，调整 right = mid - 1，因为此时 mid 可能是插入点或目标值在左半部分。

3. 终止条件：当 left > right 时，循环结束。此时 left 即为目标值的插入位置（若不存在）或目标值的位置（若存在）。

为什么返回 left？

• 存在目标值：在循环中会不断调整指针，最终 mid 命中目标值，循环结束时 left 即为目标值的位置。

• 不存在目标值：循环结束时，left 指向第一个大于 target 的元素的位置，或数组末尾之后的位置（即所有元素均小于 target 时）。

示例分析（示例2）：

• nums = [1,3,5,6], target = 2

• 初始：left=0, right=3 → mid=1，nums[1]=3 > 2 → right=0

• 下一轮：left=0, right=0 → mid=0，nums[0]=1 < 2 → left=1

• 循环结束，返回 left=1（即插入位置）。

代码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (nums[mid] < target) {
                left = mid + 1; // 目标在右半部分
            } else {
                right = mid - 1; // 目标在左半部分或mid处
            }
        }
        return left; // left即为插入位置
    }
}

复杂度分析

• 时间复杂度：O(log n)。每次循环将搜索范围减半，最多执行 log n 次循环。

• 空间复杂度：O(1)。仅使用常数级别的额外空间。

总结

通过二分查找的变体，我们巧妙地利用指针调整策略，最终返回 left 的值作为目标值的插入位置。该算法高效且简洁，完美满足了题目的所有要求。理解这一过程的关键在于明确循环结束时 left 指针的意义，即第一个大于等于目标值的位置。