搜索插入位置

搜索插入位置

问题描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

思路

我们可以使用二分查找的思想来找到 target 应该插入的位置，而不需要修改原始数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {  
public:  
    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;  // 调整右边界  
            }  
        }  
        // 循环结束时，left 指向的是第一个大于 target 的数的位置，或者如果 target 比所有数都大，则指向 nums.size()  
        return left;  
    }  
};

解释

  1. 初始化：设置两个指针 left 和 right，分别指向数组的开始和结束。
  2. 二分查找：在每次迭代中，计算中间索引mid，并比较nums[mid]和target。
    • 如果nums[mid] == target，则返回 mid。
    • 如果nums[mid] < target，则 target 在 mid 的右侧，因此将 left 更新为 mid + 1。
    • 如果nums[mid] > target，则 target 在 mid 的左侧，因此将 right 更新为 mid - 1。
  3. 返回结果：当 left 大于 right 时，循环结束。此时，left 指向的是第一个大于 target 的数的位置（如果 target 比所有数都大，则 left 指向 nums.size()）。这正是 target 应该插入的位置。

这种实现方式既高效又符合题目要求，不修改原始数组。