这道题目，要在数组中插入目标值，无非是这四种情况。

1、目标值在数组所有元素之前
2、目标值等于数组中某一个元素
3、目标值插入数组中的位置
4、目标值在数组所有元素之后
这四种情况确认清楚了，就可以尝试解题了。

暴力解法

class Solution{
public:
    int searchInsert(vector<int>& nums,int target){
        // 目标值在数组所有元素之前(如果第一个元素就比目标值大,说明目标值在应插在数组最前面)
        // 目标值等于数组中某一个元素 (如果目标值等于该数组元素，则说明找到了，返回该位置下标)
        // 目标值插入数组中的位置(如果数组某个元素大于目标值，则目标值应该安插在该位置)
        for(int ii=0;ii<nums.size();ii++){
            if(nums[ii]>=target) return ii;
        }
        //目标值在数组所有元素之后
        return nums.size();
    }
};

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

二分法

二分查找法是数组里的常用方法，彻底掌握它是十分必要的
注意这道题目的前提是数组是有序数组，这也是使用二分查找的基础条件

二分查找涉及的很多的边界条件，逻辑比较简单，就是写不好。

例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？
这里弄不清楚主要是因为「对区间的定义没有想清楚，这就是不变量」。

要在二分查找的过程中，保持不变量，也就是「循环不变量」。

写法一:左闭右闭区间

class Solution{
public:
    int searchInsert(vector<int>& nums,int target){
       int size=nums.size();
       // 定义target在左闭右闭的区间里，[left, right]
       int left=0;//定义左边界
       int right=size-1;//定义右边界

       while(left<=right){// 当left==right，区间[left, right]依然有效
           int middle=left+(right-left)/2;// 防止溢出 等同于(left + right)/2
           if(nums[middle]>target){// target 在左区间，所以[left, middle - 1]
               right=middle-1;//移动右指针
           }else if(nums[middle]<target){// target 在右区间，所以[middle + 1, right]
               left=middle+1;//移动左指针
           }else if(nums[middle]==target){
               return middle;
           }
       }
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
       return right+1;
    }
};

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

写法二：左闭右开区间

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n; // 定义target在左闭右开的区间里，[left, right)  target
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在 [middle+1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值的情况，直接返回下标
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前 [0,0)
        // 目标值等于数组中某一个元素 return middle
        // 目标值插入数组中的位置 [left, right) ，return right 即可
        // 目标值在数组所有元素之后的情况 [left, right)，return right 即可
        return right;
    }
};

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

总结：

确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。

然后在「二分查找的循环中，坚持循环不变量的原则」，很多细节问题，自然会知道如何处理了。