【Leetcode刷题】搜索插入位置

一、题目链接

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

二、思路

读题我们可以知道以下两个条件：

1. 数组是升序排列的数组
2. 无重复元素

要插入目标值，无非出现以下四种情况：

1. 目标值不在数组中，但比数组中的元素都要小

例如：

这时目标值将会插入0的位置，所以返回下标0

2. 目标值等于数组中的一个元素

例如：

这时，我们只需返回3的下标

3. 目标值不在数组中，但比数组中的某个元素大，又比某个元素小 – 即目标值将会插入数组中的位置

例如：

这时，目标值将会插入2的位置，所以返回下标2

4. 目标值不在数组中，但比数组中所有元素都大。

例如：

这时，目标值将会插入数组最后一个位置的下一个位置，返回4。

三、题解

题解一（暴力法）

思路：

遍历数组，找到第一个比target大的数，它的位置就是目标值将会插入的位置，所以返回它的下标。若target比所有数都大，则返会数组的大小。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] >= target)
                return i;
        }
        return nums.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度O(N)

由于题目要求必须时间复杂度为O(logN),所以请看下面一种方法

题解二（二分法）

思路：

由于题目中出现排序数组并且无重复元素，所以我们可以考虑是否能用二分法

若目标值在数组中，利用二分法查找目标值，这一种情况就不再多说了，若有不了解，请点击此处，进行查看，我们主要看其他三种情况

从上面三种情况的例图来看，除了在数组中的元素外，其他三种情况只需返回 右下标+1 的位置即可

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;//中间元素下标
            
            if(nums[mid] > target)
                right = mid - 1;
            else if(nums[mid] < target)
                left = mid + 1;
            else
                // nums[mid] == target
                return mid;//等于数组中的元素时，返回下标
        }

        return right + 1;//除在数组中的元素外的其他三种情况
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22