Searching and inserting in a sorted array with std::lower_bound

Once a range of data has been sorted, it becomes possible to search within that data using binary search, as opposed to the slower linear search. The standard algorithm that implements binary search is called std::lower_bound(a,b,v):

    template<class FwdIt, class T, class C>
    FwdIt lower_bound(FwdIt first, FwdIt last, const T& value, C lessthan)
    {
      using DiffT = typename std::iterator_traits<FwdIt>::difference_type;
      FwdIt it;
      DiffT count = std::distance(first, last);

      while (count > 0) {
        DiffT step = count / 2;
        it = first;
        std::advance(it, step);
        if (lessthan(*it, value)) {
          ++it;
          first = it;
          count -= step + 1;
        } else {
          count = step;
        }
      }
      return first;
    }

    template<class FwdIt, class...