搜索插入位置-数组35-C++

算法思想：

一、没看答案：

• while循环用来负责target在数组中不存在的情况下将target+1并继续搜索，直到搜索到或者超过了数组的最大值（因为数组是有序的，最大值就是数组最后一个值），并按情况返回下标索引。
• 因为target是不断增大的，所以如果target一开始就小于数组最小值，要额外判断并输出0。

C++

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

        return res;
    }
};

以上思想的改进版代码：

C++

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

        return nums.size();
    }
};

算法复杂度：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

二、二分查找：

C++

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while(left <= right){
            int middle = (left + right) / 2;
            if(nums[middle] > target){
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            }else if(nums[middle] < target){
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            }else{
                return middle;
            }
        }
		
		// 分别处理如下四种情况
        // 目标值在数组所有元素之前  right = -1 return right + 1 = 0
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
		
        return right + 1;


    }
};

算法复杂度：

• 时间复杂度：O(nlogn)。
• 空间复杂度：O(1)。