35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

注意事项：

        1.其实这题主要也是用二分搜索法，只不过稍微有一点变化，新增加了一个变量，ret，初始值必须要设为nums.size()，我一开始没注意到，就有过不了的，就是有可能target比nums[nums.size()-1]的值都要大。

        2.ret=middle，ret的值随着middle的值而变化，说到这个，也有一个middle的小细节，middle=（left+right）/2要放到while循环的内部，随着left和right的变化而变化。

        3.我一开始写的时候还没有转过弯来，没有用到二分法，写的一团乱麻，甚至连left和right的值都没有变。

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