# What is the difference between partition_point and lower_bound?

• A+
Category：Languages

c++11 includes the algorithm partition_point in the STL. However for all the cases I have tried it gives the same answer as lower_bound. The only difference being the convenient `T& value` parameter. Did I miss something or are these two functions doing more or less the same thing?

They both use a binary search algorithm (for random access iterator).

• `std::lower_bound` requires that the range to be sorted according to (binary) predicate partitioned with respect to the expression `element < value` or `comp(element, value)` (which is the case if range is sorted according to binary predicate).
• `std::partition_point` requires that the range is partitioned according to the (unary) predicate.

You can indeed create a predicate to be able to use the other algorithm.

With:

``const std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8}; ``

You can do with `lower_bound`:

``assert(std::is_sorted(v.begin, v.end(), std::less<>)); auto it1 = std::lower_bound(v.begin, v.end(), 5, std::less<>); ``

or with `partition_point`:

``auto pred = [](int e){ return e < 5; } assert(std::is_partition(v.begin, v.end(), pred)); auto it2 = std::partition_point(v.begin, v.end(), pred);  assert(it1 == it2); // *it1 = 5 ``

Or, with the other side

``const std::vector<int> v{1, 3, 4, 2, 7, 5, 8, 6}; ``

You can do with `partition_point`:

``auto pred = [](int e){ return e < 5; } assert(std::is_partition(v.begin, v.end(), pred)); auto it1 = std::partition_point(v.begin, v.end(), pred); ``

or with `lower_bound`:

``auto pred2 = [](int lhs, int rhs){ return (lhs < 5) > (rhs < 5); } assert(std::is_sorted(v.begin, v.end(), pred2)); auto it2 = std::lower_bound(v.begin, v.end(), 5, pred2);  assert(it1 == it2); // *it1 == 7 ``