35. 搜索插入位置，讲清楚二分

关于最后为什么return left，其实可以这么理解，没有找到时，l与r肯定反了，不够成区间，且相差不会超过1，跳出前的情况可以分为一下两种：

lr相等(l == r == mid)

1. 此时有可能是l右移超过了r，那l=mid +1，mid肯定是小于target了，那现在mid+1就是第一个不小于target可以插入的位置，为啥不是r呢，发生交叉时l与r是相等的，那既然是l右移，说明r是最后一个小于target的数(return left)
2. 反过来，如果r=mid-1，导致lr反叉，则mid是大于了target的，则mid-1是最后一个小于target的数，那mid-1的下一个位置就是插入位置，即l

lr差一(l=mid,r=l+1)

1. 最后如果是L往右移l=mid+1会相遇，即跳到是上面的l == r == mid情况
2. 如果是r左移 那就会直接反转了，相差为 1，则mid是大于了target的 ,
   则mid-1是最后一个小于target的数，那mid-1的下一个位置就是插入位置，即l

综上可以return left 或 right+1

这些其实原理是在：所有的lr反转前lr肯定是相遇了或差一的时候反的，然后另外一个核心是mid是向下取整重叠到l的，这才有上面的结果。

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