📝 题目描述

题目链接：搜索插入位置

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

请必须使用时间复杂度为 O(logn)O(log n) 的算法。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 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

提示：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 为 无重复元素 的 升序 排列数组
  • -10^4 <= target <= 10^4

💡 解题思路

方法一：二分查找

题目通过非常简单，使用基础的二分查找即可通过所有测试用例，这里分析一下为什么返回 i 而不是 j。

核心结论：

在代码中，循环的终止条件是 i > j（具体来说，循环结束的那一刻，一定是 i = j + 1）。
如果目标值 target 在数组中不存在，当循环结束时：

  • i（左指针）：始终指向第一个大于 target 的元素的位置。这也是 target 按顺序应该被插入的位置。
  • j（右指针）：始终指向最后一个小于 target 的元素的位置。

既然需要把 target 插入到比它小的元素之后、比它大的元素之前，那么插入位置恰好就是当前 i 所在的位置。

推导：

在循环结束前的最后一轮。在最后一轮循环开始时，必然有 i == j。假设此时它们的索引都是 k。

此时，中点自然也是 k。我们拿 nums[k] 和 target 进行比较，因为 target 不在数组中，所以只有两种情况：

情况 1：nums[k] < target

说明 target 应该插入在 nums[k] 的右侧（也就是 k + 1 的位置）。

  • 根据代码，会执行 i = k + 1。
  • 此时 i 变成了 k + 1，而 j 依然是 k。
  • 循环因为 i > j 结束。

结果：目标应该插入在 k + 1 的位置，而此时刚好 i = k + 1。所以返回 i 是正确的。（如果返回 j，返回的就是 k，位置偏左了）。

情况 2：nums[k] > target

说明 target 比当前元素还要小，它应该插入在 nums[k] 的当前位置，把 nums[k] 及后面的元素全部向右挤一位（也就是插入在 k 的位置）。

  • 根据代码，会执行 j = k - 1。
  • 此时 j 变成了 k - 1，而 i 依然是 k。
  • 循环因为 i > j 结束。

结果：目标应该插入在 k 的位置，而此时刚好 i = k。所以返回 i 是正确的。（如果返回 j，返回的就是 k - 1，位置同样偏左了）。

结合示例 2 来看：

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

  1. 初始状态：i = 0, j = 3

    • k = 0 + (3-0)/2 = 1
    • nums[1] 是 3。因为 3 > 2，执行 j = k - 1 = 0。

  2. 第二轮循环：i = 0, j = 0 （此时 i == j，这就是上面提到的最后一轮）

    • k = 0 + (0-0)/2 = 0
    • nums[0] 是 1。因为 1 < 2，执行 i = k + 1 = 1。

  3. 循环结束：i = 1, j = 0

    • 此时 i > j，跳出 while 循环。

我们要把 2 插入到 [1, 3, 5, 6] 中，显然应该插在 1 和 3 之间，也就是索引为 1 的位置。
观察结束时的指针：i = 1，刚好是插入位置；而 j = 0，指向的是小于 2 的最后一个元素。

🔧 代码实现

1、二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int i = 0, j = nums.size() - 1;
        while(i <= j) {
            int k = i + (j - i) / 2;
            if (nums[k] > target) {
                j = k - 1;
            } else if (nums[k] < target) {
                i = k + 1;
            } else {
                return k;
            }
        }
        return i;
    }
};

📊 复杂度分析

1、二分查找

  • 时间复杂度：O(logn)O(logn)，其中 n 为数组的长度，这是二分查找所需的时间复杂度为。
  • 空间复杂度：O(1)O(1)，我们只需要常数空间存放若干变量。

🎯 总结

  • 核心思想：理解为什么返回 i 。