I'm trying to create a custom comparison function for the binary search method lower_bound(). I've tried reading the docs and searching, but I can't figure out how the arguments of the comp function should be ordered.

Firstly, in the regular two-argument comp, which one is val (the target value) and which one is the item from the vector?

Secondly, how can I include more arguments?

I have a vector<int>. What I want my comp to do is take the val, subtract the vector item, and return true if the result is greater than an integer y (this cannot be done as a global variable as it changes frequently).

For example, say I have a vector<int> a = {1, 3, 5, 6, 8, 10, 11}. Given that the target value is 41, and y = 31, I want to find the last number in the vector where 41 - (number) <= 31. Since 41 - 10 = 31 then that number is 10, at index 5.

How can I build such comparators?

Please tell me if this needs more clarification. All I'm looking for is an explanation of how the comparator is built. If such a tutorial (with a very clear explanation) already exists, please point me to it, as my search has not yielded anything helpful.

TIA.

Edit: Again, I have already read the docs. I do not understand from them how to build a comp, so please stop repeating what the docs say. If you can, please explain the concept in detail. My issue is not lack of searching, but lack of understanding what I found while searching.

I'm trying to create a custom comparison function for the binary search method lower_bound(). I've tried reading the docs and searching, but I can't figure out how the arguments of the comp function should be ordered.

Firstly, in the regular two-argument comp, which one is val (the target value) and which one is the item from the vector?

Secondly, how can I include more arguments?

I have a vector<int>. What I want my comp to do is take the val, subtract the vector item, and return true if the result is greater than an integer y (this cannot be done as a global variable as it changes frequently).

For example, say I have a vector<int> a = {1, 3, 5, 6, 8, 10, 11}. Given that the target value is 41, and y = 31, I want to find the last number in the vector where 41 - (number) <= 31. Since 41 - 10 = 31 then that number is 10, at index 5.

How can I build such comparators?

Please tell me if this needs more clarification. All I'm looking for is an explanation of how the comparator is built. If such a tutorial (with a very clear explanation) already exists, please point me to it, as my search has not yielded anything helpful.

TIA.

Edit: Again, I have already read the docs. I do not understand from them how to build a comp, so please stop repeating what the docs say. If you can, please explain the concept in detail. My issue is not lack of searching, but lack of understanding what I found while searching.

• c++
• stl
• comparison
• binary-search
• lower-bound

• See std::lower_bound. – Some programmer dude Commented Jan 19 at 11:55
• @Someprogrammerdude As I mentioned, I've already read that page, in addition to multiple lower_bound() tutorials. – Aya Noaman Commented Jan 19 at 11:56
• 2 For "extra args" you can use a lambda with captures instead of actual arguments. – Some programmer dude Commented Jan 19 at 13:40
• 2 @AyaNoaman As explained in the reference, bool(comp(elem, value)). The first argument is the element in your vector. – john Commented Jan 19 at 13:55
• 1 val - elem > y is equivalent to elem < val - y. Just pass val - y instead of val as the value to test against and use std::less as the comparator. – Pete Becker Commented Jan 19 at 15:48

2 Answers 2

when using std::lower_bound(), the comparison function typically takes two parameters: the first is the item from the vector, and the second is the target value (val). This means your comparison function should be structured as comp(const int& item, const int& val).

To include additional parameters, you can use a lambda function or a std::function that captures the necessary variables. Here’s an example of how to implement your custom comparison function:

 auto compGreater = [y](const int& item, const int& val) {
        return (val - item) > y;
    };

What I want my comp to do is take the val, subtract the vector item, and return true if the result is greater than an integer y

The requirement for std::lower_bound and its comp argument is that the vector is sorted by the same comp order. That implies that comp must encode an order.

Technically, your comp does exactly that. It sorts integers in two groups, "greater than y" and "not greater than y". In other words, y is equal to y-1, and y+1 is equal to y+2. That is what you're telling std::lower_bound.

And if your vector is sorted like that, then there's no Undefined Behavior. std::lower_bound will return an iterator into the correct half of the vector. For val<=y it will an iterator somewhere into the smaller half, for val>y in the other half.

But this is probably not what you want. The mental problem you appear to be struggling with is that you try to define comp in terms of what you think it should return (return (x-val)<y), instead of thinking about the vector order, and what element to find.

And to be honest, your description is so vague that I can't even tell which element you want to find. Given {1, 5, 9, 23} and y=6, I have no idea which element you want.