35. 搜索插入位置

使用二分法

class Solution {
    
public:
    int searchInsert(vector<int>& nums, int target) {
    
       int low=0,high=nums.size()-1,middle;
       while(low<=high)//当left==right，区间[left, right]依然有效
       {
    
           middle=(low+high)/2;
           if(target<nums[middle])
           {
    
               high=middle-1;
           }
           else if(target>nums[middle])
           {
    
               low=middle+1;
           }
           else
           {
    
               return middle;// 数组中找到目标值的情况，直接返回下标
           }
       }
       return high+1;
    }
};

时间复杂度：O(logn)
空间复杂度：O(1)