35. 搜索插入位置

搜索插入位置

原题：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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

解题方法：

解法一：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++)
        {
            if(target<=nums[i])
            {
                return i;
            }
        }
        return nums.size();
    }
};

解法二：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;            //左闭右闭，根据循环不变量，后续也需要保持左闭右闭
        while(left<=right)
        {
            int middle=left+(right-left)/2;
            if(nums[middle]>target)        //target应在左边
            {
                right=middle-1;
            }
            else if(nums[middle]<target)
            {
                left=middle+1;
            }
            else
            {
                return middle;
            }
        }
        return right+1;

    }
};


class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size();            //左闭右开，根据循环不变量，后续也需要保持左闭右开
        while(left<right)
        {
            int middle=left+(right-left)/2;
            if(nums[middle]>target)        //target应在左边
            {
                right=middle;
            }
            else if(nums[middle]<target)
            {
                left=middle+1;
            }
            else
            {
                return middle;
            }
        }
        return right;                    //此处的变化需要注意         

    }
};

做题小结：

针对解法一：

1. 暴力，时间复杂度O(n),空间复杂度O(1)

针对解法二：

1. 二分查找法的条件是数组有序且一般不存在重复值，如果存在重复值就需要对二分查找进行一定的调整
2. 要确定循环不变量，如此处选择right=nums.size()-1 ，那么target的寻找范围就为[left,right]这样一个左闭右闭区间，那么就应该用left<=right进行循环结束判准，因为left是可以等于right的。后面right就应该等于middle-1（区间变为[left,middle-1]）或者left变为middle+1（区间变为[middle+1,right]），始终还是左闭右闭
3. 与2同理，如果选择了right=nums.size()，那么就是左闭右开区间，后面的循环结束判准，和right的变化都应响应修改