搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。

如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

必须使用时间复杂度为 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

提示：

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

二分查找：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();

        while (left < right)
        {
            int mid = left + (right - left) / 2;

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

        return left;
    }
};

核心思想

数组已经按照升序排列，因此可以使用二分查找快速缩小目标位置。

如果每个元素都顺序比较，最坏时间复杂度是 O(n)，不满足题目要求。

这题的目标不只是判断 target 是否存在，还要在不存在时找到它应该插入的位置。

这个位置可以统一定义为：

数组中第一个大于等于 target 的下标。

如果数组中存在 target，这个下标就是它的位置。

如果数组中不存在 target，这个下标前面的所有元素都小于 target，把 target 插入这里后数组仍然有序。

如果所有元素都小于 target，则不存在大于等于 target 的元素，应该返回数组长度 n，表示插入到数组末尾。

因此只需要用二分查找寻找第一个满足：

nums[index] >= target

的位置。

区间定义

代码使用左闭右开区间：

[left, right)

它表示答案一定在下标 left 到 right - 1 之间。

初始化时：

int left = 0;
int right = nums.size();

答案可能是数组中的任意位置，也可能是数组长度 n，所以右边界要设置为 n，而不是 n - 1。

例如 target 大于数组中的所有元素时，正确答案是 n。

这个答案虽然不是数组元素下标，但它是合法的插入位置，因此必须包含在搜索范围内。

二分查找逻辑

每次取中点：

int mid = left + (right - left) / 2;

使用这种写法可以避免直接计算 (left + right) / 2 时可能发生的整数溢出。

nums[mid] >= target

说明 mid 已经满足“值大于等于 target”这个条件。

但 mid 可能不是第一个满足条件的位置，答案还可能在它左边。

因此保留 mid，收缩右边界：

right = mid;

nums[mid] < target

说明 mid 以及它左侧的所有元素都小于 target。

它们不可能是第一个大于等于 target 的位置。

因此答案只能在 mid 右侧，收缩左边界：

left = mid + 1;

为什么使用 right = mid 而不是 right = mid - 1

当 nums[mid] >= target 时，mid 自己可能就是答案。

所以不能把 mid 排除掉，只能令：

right = mid

例如：

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

如果 mid 指向值 5 的位置，答案就是 mid。

如果写成 right = mid - 1，就会把正确答案排除。

相反，当 nums[mid] < target 时，mid 一定不可能是答案，所以可以安全地令：

left = mid + 1

循环结束条件

循环条件是：

while (left < right)

当 left == right 时，搜索区间 [left, right) 为空。

此时 left 就是第一个大于等于 target 的位置，或者是数组长度 n。

所以直接返回：

return left;

不需要额外判断 target 是否真的存在。

为什么数组有序很重要

二分查找依赖数组的升序性质。

当发现 nums[mid] < target 时，只有因为数组有序，才能确定 mid 左侧的所有元素也都小于 target。

这样才能一次排除左半部分。

同理，当 nums[mid] >= target 时，才能保留左半部分并排除右侧部分。

如果数组无序，就无法根据一个中点元素判断哪一半可以被排除，也就不能使用这种二分方法。

边界情况

如果 target 等于数组第一个元素，二分查找最终返回 0。

如果 target 小于数组中的所有元素，所有元素都需要向右移动，插入位置是 0。

如果 target 等于数组最后一个元素，返回最后一个元素的下标。

如果 target 大于数组中的所有元素，返回 nums.size()，表示插入到数组末尾。

如果 target 位于两个元素之间，例如：

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

第一个大于等于 2 的元素是 3，所以返回下标 1。

题目保证数组没有重复元素，因此找到的目标值位置是唯一的。

即使数组允许重复元素，这种写法仍然会返回第一个大于等于 target 的位置。

正确性证明

我们证明：算法返回的 left 正好是 target 在数组中的位置，或者是它应该被插入的位置。

结论 1：答案始终位于当前搜索区间 [left, right) 中

初始时，搜索区间是 [0, n)。

答案可能是数组中的任意下标，也可能是 n，所以答案一定在初始区间的边界范围内。

每次循环有两种情况。

如果 nums[mid] >= target，mid 可能是答案，算法令：

right = mid

新的区间 [left, mid) 保留了 mid 以及左侧可能的答案位置在区间边界中。

这里的左闭右开区间把 right 作为候选边界，不会错误排除第一个满足条件的位置。

如果 nums[mid] < target，由于数组升序，mid 及其左侧都小于 target，不可能是答案。

算法令：

left = mid + 1

因此真正的答案仍然在新的 [mid + 1, right) 中。

所以每次更新后，答案都不会被排除。

结论 2：left 左侧的所有元素都小于 target

初始时 left = 0，它左侧没有元素，结论成立。

如果某次因为 nums[mid] < target 执行：

left = mid + 1

由于数组升序，mid 以及它左侧的所有元素都小于 target。

所以新的 left 左侧所有元素仍然小于 target。

如果某次更新的是 right，left 不变，结论也继续成立。

因此循环过程中，left 左侧始终没有任何可以作为答案的元素。

结论 3：right 及其右侧包含的元素中，存在满足条件的位置，或 right 是数组末尾

如果 right = n，它表示答案可能是数组末尾的插入位置，结论成立。

如果因为 nums[mid] >= target 执行：

right = mid

那么 mid 本身满足大于等于 target，所以把它作为新的右边界后，答案不会被排除。

如果因为 nums[mid] < target 更新 left，right 不变，原有结论继续成立。

因此，右边界始终不会越过真正的第一个满足条件的位置。

结论 4：循环结束时，left 是第一个大于等于 target 的位置

循环结束时：

left == right

由结论 2 可知，left 左侧的所有元素都小于 target。

由结论 3 可知，如果 left < n，则 nums[left] >= target；如果 left == n，则说明数组中没有大于等于 target 的元素。

因此：

• 当 left < n 时，left 是第一个满足 nums[left] >= target 的位置。
• 当 left == n 时，所有元素都小于 target，插入位置就是数组末尾。

所以循环结束时返回 left 是正确的。

得出结论

由结论 1 可知，二分过程中不会排除真正答案。

由结论 2 可知，返回位置左侧的元素都小于 target。

由结论 3 可知，返回位置本身满足条件，或者它是数组末尾。

由结论 4 可知，循环结束时 left 正好是第一个大于等于 target 的位置。

因此算法能够正确返回目标值下标或目标值的插入位置。

举例理解

以：

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

为例。

初始搜索区间是：

[left, right) = [0,4)

执行过程如下：

此时：

left = right = 1

下标 0 的值 1 小于 2，下标 1 的值 3 大于 2。

所以 2 应该插入下标 1，算法返回：

1

再看 target = 7 的情况。

二分查找会不断排除数组中的所有元素，最后得到：

left = right = 4

这表示 7 应该插入数组末尾，返回 4。

复杂度分析

每次二分都会把搜索区间缩小到原来的一半左右。

因此最多进行 O(log n) 次比较。

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

算法只使用了 left、right 和 mid 等常数个变量，没有创建额外数组。