一.题目描述
35. 搜索插入位置 - 力扣（LeetCode）
二.题目解析
如果只看题目的前半句，直接就用简单二分秒了。但是题目还有后半句，如果找不到目标值，则返回它应该插入的位置。
因为数组是排序的，所以应该插入的位置就是target插入之后，依旧满足数组是有序的。
三.算法原理
1.暴力解法
我们先遍历一边数组，看target是否存在。如果不存在，我们就在遍历一边数组，找到第一个大于target的元素，返回该元素的下标即可。
时间复杂度：遍历了两边数组，所以时间复杂度为O(N)
空间复杂度：遍历过程中只是用了有限个变量，所以空间复杂度为O(1)
2.二分算法
查找一个数在不在我们可以用简单二分来解决，但是这道题涉及到如果不存在，需要返回待插入的位置，所以简单二分是解决不了的。
我们可以对数组进行分析，target会将数组分为两个部分，[0~target]<=target，[target+1,size-1]>target。这样的划分规则就类似于二分查找中——查找区间右端点，所以我们可以根据此二段性，利用查找区间的右端点来解决问题。
查找完成后，会剩余一个元素，该元素要么是target，要么不是。如果不是的话，又分为两种情况，当前元素小于target，此时我们就应该插入下一个位置；如果当前位置>target，说明插入到该元素位置即可。
四.代码实现
// C++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-left+1)/2;if(nums[mid] > target){right = mid-1;}else{left = mid;}}if(nums[left] < target){return left+1;}return left; }
};# pythonclass Solution:def searchInsert(self, nums: List[int], target: int) -> int:left,right = 0,len(nums)-1while left<right:mid = left+(right-left+1)//2if nums[mid] > target:right = mid-1else:left = midif(nums[left] < target):return left+1return left