leetcode_35.搜索插入位置

题目如下：

首先这个题暴力也可以过，但是题目要求我们使用O(log n)时间复杂度的算法,所以我们这道题还是试用二分的方式来解决，依旧是往期的两个模板，这里我们都写一下
左闭右开

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l=0,r=nums.size();while(l<r){int mid=(l+r)>>1;if(nums[mid]>target){r=mid;}else if(nums[mid]<target){l=mid+1;}else return mid;}return l;}
};

左闭右闭

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){r=mid-1;}else if(nums[mid]<target){l=mid+1;}else return mid;}return l;}
};

最后附上暴力做法：

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

暴力的代码我来说一下，主要就是遍历整个数组，通过寻找第一个大于等于target的值，等于的话就是找到了这个元素，直接返回其下标，大于的话等于就是这个元素必须插入到这里。最后循环结束，没有找到的话，表明target大于数组中的所有元素，返回这个数组最后一个位置就Ok了