LeetCode 35. 搜索插入位置

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析 

该题我们可以采用二分查找的方式，我们可以把数组分为，小于target的一边儿和大于等于target的一边儿。

当mid=left+(right-left)下标所对应的数大于等于target的时候，说明target落在了mid的左边，因此应该改变right=mid;

当mid=left+(right-left)下标所对应的数小于target的时候，说明target落在了mid的右边，此时应改变left=mid+1;

最后考虑一下如果target大于该数组的最后一个元素的时候应该返回的下标。

代码

class Solution 
{
public:int searchInsert(vector<int>& nums, int target) {int n=nums.size();int left = 0,right=n-1;// 设target的下标为index// 小于target的[left,index-1]// 区间分为大于等于target的 [index,right]while(left<right){int mid=left+(right-left)/2;// 该if条件成立说明mid落在了[index,right]// 因此应该改变右边界if(nums[mid]>=target)right=mid;// 该else条件成立说明mid落在了[left,index-1]// 因此应该改变左边界else left=mid+1;}if(nums[left]<target) return right+1;return left;}
};