35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
二分算法
简单写一个二分法，然后最后判断如果数要插入后位置应该是最后找到的位置r的左边还是右边（即判断target和nums[r]的大小）
1.向上取整的写法
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<r){
int mid=(l+r)>>1;
if(nums[mid]==target)return mid;
else if(nums[mid]>target)r=mid;
else l=mid+1;
}
return target>nums[r]?r+1:r;
}
};
2.向下取整的写法
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<r){
int mid=(l+r+1)>>1;
if(nums[mid]==target)return mid;
else if(nums[mid]>target)r=mid-1;
else l=mid;
}
return target>nums[r]?r+1:r;
}
};
写法的区别在于你的check函数(也就是判断找到的点是不是符合要求)的结果判断,是需要向上还是向下取整。
这道题是没有特殊要求，也就是哪种都可以，最后结果取决于你找到的nums[r]和target的大小决定把target放在哪边。
其最终本质都是为了不重复的划分区间以二分找到最后的边界。也就是之前说的二分的本质是划分性，有序只是一个特征。