这道题使用二分查找,先排除特殊情况,当左指针大于等于右指针时说明所有元素查找完毕,如果target与nums[i]相等,则数组中存在target,返回i,否则返回i+1。

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