leetcode 35: search inserted position

Given a sorted array 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 may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

这题找应该插入的位置，可以首先找到与target closest的元素position，在这一题中不需要获得特别精确的closest element，与纯粹找closest 不一样，这题只需要确定closest一个大致的位置即可，然后通过判断确定插入在这个位置上或者这个位置后面。可以先通过binary search找到一个closest 的position，即最后left所指向的内容，然后判断left 的值与target的大小，如果left >= target，那么target应该插在left位置上，否则target应该插在left后面。   

为什么要这样做呢？
因为如果target 找不到， 最终跳出while 循环，left 和right只有两种可能关系： 1. left = right, 2. left = right-1; 因为： left = mid + 1; right = mid -1;最终没有找到的时候，left == mid， 所以造成了最后left 和right的关系，left == right是当target > mid的时候，left向右移， ｌｅｆｔ＝　ｍｉｄ＋１，再比较ｔａｒｇｅｔ　和ｌｅｆｔ的大小，如果大则插入位置在ｌｅｆｔ右侧，如果小，则插入在ｌｅｆｔ的位置。

时间复杂度为o(logn)

class Solution {
public:
//binary search
    int searchInsert(vector<int>& nums, int target) {
        //sanity check
        if (nums.size() == 0) return 0;
        int left = 0;
        int right = nums.size()-1;
        //find closeset elemnte
        while (left < right) {
            int mid = left + (right - left)/2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid -1;
            } else return mid;
        }
        //left is the closest num of target
        if (target <= nums[left]) {
            return left;
        }else if (target > nums[left]){
            return left + 1;   
        }
    }
};