0035.Search-Insert-Position

搜索插入位置

1. 题目

1.1. 描述

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

1.2. 示例

示例 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.3. 提示

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

2. 思路

2.1. 迭代法

• 遍历数组，寻找第一个大于等于给定值的元素索引，若找不到索引则返回数组长度
• 时间复杂度为O(n)，空间复杂度为O(1)

2.2. 二分法

• 设置变量left，right，在区间[left..right]里查找第一个大于等于target的元素下标
• 时间复杂度为O(logn)，空间复杂度为O(1)

3. 代码

3.1. C++

3.1.1. 迭代法

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        for (int i = 0; i < len; i++)
        {
            if(nums[i]>=target){
                return i;
            }
        }
        return len;
    }
};

3.1.2. 二分查找

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        while(left<right)
        {
            int mid = (left+right)/2;
            // 中间的元素和target 相等，直接返回下标
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                // 中间的元素小于target
                // [left,mid]区间中的所有元素都小于target
                // 缩小查找区间为[mid+1,right]
                left=mid+1;
            }else{
                // 中间的元素大于target
                // [mid,right]区间中的所有元素都大于target
                // 缩小查找区间为[left,mid-1]
                right=mid-1;
            }
        }
        // 退出while时在数组中没有找到和target相同元素
        // 此时left=right=mid
        // 若nums[mid]>=target，target顶替nums[mid]的位置，[mid,right]的元素后移，left指向nums[mid]元素位置
        // 若nums[mid]<target，target插入nums[mid]后一个位置left+1
        return nums[left]>=target?left:left+1;
    }
};

3.2. Java

3.2.1. 迭代法

class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        for (int i = 0; i < len; i++)
        {
            if(nums[i]>=target){
                return i;
            }
        }
        return len;
    }
}

3.2.2. 二分查找

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left<right){
            int mid = (left+right)/2;
            if(nums[mid]>=target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}