【C++刷题】力扣-#35-搜索插入位置

题目描述

给定一个已排序的数组 nums 和一个目标值 target，你需要找出 target 在数组中的插入位置，以保持数组的有序性。如果
target 已经存在于数组中，则返回它的索引。

示例

示例 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。

题解

这个问题可以通过二分查找来解决，因为数组是已排序的。

1. 初始化：设置两个指针 left 和 right 分别指向数组的开始和结束。
2. 二分查找：在 left 和 right 之间进行二分查找。
   ○ 如果 nums[mid] 等于 target，则返回 mid。
   ○ 如果 nums[mid] 小于 target，则将 left 设置为 mid + 1。
   ○ 如果 nums[mid] 大于 target，则将 right 设置为 mid - 1。
3. 返回结果：如果 target 不在数组中，则 left 将指向 target 应该被插入的位置。

代码实现

int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left; // 返回插入位置
}

复杂度分析

● 时间复杂度：O(log n)，其中 n 是数组 nums 的长度。这是因为我们使用了二分查找。
● 空间复杂度：O(1)，因为我们没有使用额外的空间。
这个算法的优势在于它利用了数组的有序性，通过二分查找快速定位目标值的插入位置。