35. Search Insert 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

解法 :
         看到有排序又要你找裡面的東西，二話不說，一定就是binary search的概念
 如果找不到，再將target加入nums中再排序一次後，一樣用binary search。
而C++11有提供了 binary search的演算法，有分lower_bound以及upper_bound

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        
        //利用binary search去找
        auto first = std::lower_bound(nums.begin(), nums.end(), target);
        
        //沒有就加入
        if (first == nums.end())
        {
           //加入後sort
            nums.push_back(target);
            sort(nums.begin(), nums.end());
                        
            //再一次binary search去找
            first = std::lower_bound(nums.begin(), nums.end(), target);

        }
        
        //最後iterator跟begin相減就知道是第幾個了
        return first - nums.begin();
    }
};