搜索插入位置

Leetcode.35

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

实际上是 二分查找 plus，关键是领悟如果结果不存在，此时应该返回的下标是left还是right或是left+1，right+1，middle。个人经验是在给定的实例里面脑算试一下，得到是到底应该返回哪个。
答案是用二分查找的开区间模式最终返回right即可。

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

相关知识点： 二分查找