Doubt regarding Comparator

#1

I don’t really understand how the comparator is working in this case as in the return statement he has typed a<=b then why is there a need to -1 at the end on the lower bound index, shouldn’t we have automatically gotten the lower index because of the comparator??

#2

Please note that this was just an example to show how to use comparators in binary search.

Now, realize that the answer we want is basically

upper_bound(...) - coins - 1

If this part is clear let me know, I’ll explain further, else I’ll clear this.

#3

I do get that it can be done with upper_bound(…) -coins -1

#4

but I don’t understand how is the comparator working in this case. If you could please explain that, it would be helpful

#5

Okay, now, let’s see how lower_bound works, lower_bound finds the first such value in the array for which (value < target_value) is false, where ‘<’ is basically the comparator.

Therefore, we can see that it finds the first value larger than or equal to the target value.

Reply, if this is clear, I’ll then proceed.

#6

Now, the comparator is changed to ‘<=’ which means the first value where (value <= target_value) is false, note that this returns the first larger value than the target value (and not equal to), and this is same as upper_bound().

Therefore, this is same as what you wanted.

#7

In other words, std::lower_bound with default < being replaced with <= is exactly what std::upper_bound with default < is.

#8

Thanks, My doubt is clear now.

1 Like