LCR 068. 搜索插入位置 - 力扣（LeetCode）

题目要求：

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

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

示例 4:

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

示例 5:

输入: nums = [1], target = 0
输出: 0

提示:

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

暴力枚举 O(N)：

        只需要枚举nums数组，只要第一次发现某个元素大于等于target，那么这个元素的下标就是target应该插入的位置。

        如果找不到，说明target比nums的最大值还大，返回nums.size()即可。

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();}
};

二分查找(查找右端点) O(LogN)：

        根据暴力枚举算法，可以发现返回值对应的元素把nums分成了左边(不包括返回值)：小于target的部分和右边(包括返回值)：大于等于target的部分。

        因为返回值对应的元素可能大于或等于target，所以要查找右端点。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0,right = nums.size()-1;if(target>nums.back()) return nums.size();while(left<right){int mid = left+(right-left)/2;if(nums[mid]<target)left=mid+1;else if(nums[mid]>=target)right=mid;elsereturn mid;}return right;}
};