题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2
示例 2:
输入: [1,3,5,6], 2 输出: 1
示例 3:
输入: [1,3,5,6], 7 输出: 4
示例 4:
输入: [1,3,5,6], 0 输出: 0
解题
方法一：直接遍历(i)
如果索引为i对应的值和目标值，相等就返回该索引。如果大于，那么久在该值前插入，插入的位置也是i。如果没有存在这样的情况，那么就在末尾插入，返回的是i+1
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: for i in range(len(nums)): if nums[i]>=target: return i return i+1
方法二：二分查找
python解法
二分查找，还需要对特殊情况进行判断。
if nums[mid]>=target: right = mid
由于这个索引（mid）很可能是我们需要返回的内容，如果right = mid-1,就越过了这个解，后续就再也没办法找到了。
对于二分查找，这种-1，+1，这种细节特别重要
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left = 0 right = len(nums)-1 #特殊情况判断 if target>nums[right]: return right+1 while left<right: mid = (left+right)//2 if nums[mid]>=target: right = mid else: left = mid+1 return left
也可以改写一下，right的初始值，就不需要特殊判断了。
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) while left<right: mid = (left+right)//2 if nums[mid]>=target: right = mid else: left = mid+1 return left
c++解法 (重要)
class Solution { public: int searchInsert(vector<int>& nums, int target) { int n=nums.size(); int left=0,right=n-1; while(left<=right){//一定要等于号,否则left还没找到插入位置的时候，right落在left上，那么就会中断 int mid=left+(right-left)/2; if(nums[mid]<target){//如果加入等号，left都会停在target右侧 left=mid+1; } else{ right=mid-1; } } return left; } };
