LeetCode: 35. 搜索插入位置 #80

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
    
    template<typename ForwardIterator, typename T>
    ForwardIterator lower_bound (ForwardIterator first,
                                ForwardIterator last,
                                T value) {
        while (first != last) {
            auto mid = next(first, distance(first, last) / 2);
            
            if (value > *mid)
                first = ++mid;
            else
                last = mid;
        }
        return first;
    }
};