c++使用std::find实现lower_bound

使用`std::find`实现`std::lower_bound`的算法时间复杂度是$O(n)$，不如STL中的`std::lower_bound`的时间复杂度是$O(\log n)$。不过，这里仍然展示一下如何使用`std::find`实现`std::lower_bound`。

#include <iostream>
#include <vector>
#include <algorithm>

template<typename ForwardIt, typename T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    while (first != last && *first < value) {
        ++first;
    }
    return first;
}

int main()
{
    std::vector<int> v{ 1, 2, 2, 3, 4, 5 };
    auto it = lower_bound(v.begin(), v.end(), 3);
    std::cout << "Lower bound of 3 is " << std::distance(v.begin(), it) << std::endl;
    return 0;
}

输出：

Lower bound of 3 is 3

这个实现的思想类似于二分查找，但是实现方式略有不同，可以说是一种仿佛二分查找的实现。如果元素个数比较少的话，这个实现的速度也应该是足够快的。