0035.搜索插入位置

难度：🟢 简单

标签：数组、二分查找

链接：35. 搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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 指向数组的起始位置（索引 0），right 指向数组的结束位置（索引 nums.length - 1）。这两个指针构成了我们的搜索区间 [left, right]。

2. 循环条件：当 left <= right 时，表示搜索区间仍然有效，持续循环。

3. 计算中间点：计算中间索引 mid = left + Math.floor((right - left) / 2)。

4. 比较与收缩区间： a. 如果 nums[mid] 等于 target，说明找到了目标值，直接返回 mid。 b. 如果 nums[mid] 小于 target，说明目标值应该在 mid 的右侧，因此我们将搜索区间的左边界更新为 left = mid + 1。 c. 如果 nums[mid] 大于 target，说明目标值应该在 mid 的左侧，因此我们将搜索区间的右边界更新为 right = mid - 1。

5. 返回插入位置：如果循环结束时仍未找到 target，此时 left 指针所在的位置就是 target 应该被插入的位置。这是因为 left 最终会停在第一个大于等于 target 的元素的位置上。

代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 循环结束时，left 指向的就是插入位置
    return left;
};

复杂度分析

• 时间复杂度：O(log n) 其中 n 是数组 nums 的长度。每一次比较都将搜索范围缩小一半，所以时间复杂度是对数级别的。

• 空间复杂度：O(1) 我们只使用了 left, right, mid 等常数个额外变量，空间消耗是恒定的。

相关题目

• 0704.二分查找

• 0034.在排序数组中查找元素的第一个和最后一个位置

总结

本题是二分查找算法的经典变种应用。它不仅考察了标准的二分查找过程，更重要的是考察了对算法循环终止时，指针状态的理解。理解为什么当目标值不存在时，left 指针恰好是正确的插入位置，是掌握此题的关键。