What is the complexity for std::upper_bound and std::lower_bound for Vector in C++?

Question

What is the complexity of the std::lower_bound and std::upper_bound functions.

I know in case of std::set<int> it is log(n), but I have no idea for a std::vector<int>.

I was going through an implementation of the Longest Increasing Subsequence using vectors and std::lower_bound.

What is the complexity of this code?

int LIS2(vector<int> a) {
    vector<int> v;
    for (int i = 0; i < a.size(); i++) {
        auto it = lower_bound(v.begin(), v.end(), a[i]);
        if (it != v.end()) 
            *it = a[i];
        else 
            v.push_back(a[i]);
    }
    return v.size();
}

Answer 1

From https://en.cppreference.com/w/cpp/algorithm/lower_bound:

Complexity

The number of comparisons performed is logarithmic in the distance between first and last (At most log₂(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

For random access iterators (e.g from std::vector) the bounds functions simply do a binary search.

For non-random access iterators (e.g. from std::list and std::set) the functions still perform a binary search but there is an additional cost as they have to increment the iterators one element at a time to move between elements.