Code not understood

#1

I have problem here in understanding the implementation of lower_bound function using comparator.
When we have defined comparator function as returning a<=b then why we have to subtract 1 from the iterator ,thats the issue.
If we are not subtracting 1 then lower_bound with custom comparator as shown in video is returning iterator to element greater than that element,then how is comparator function working.

#2

hi @aayuushh,
if we dont use comparator, then the lower bound function gives the first value in the sorted array that is greater than or equal to the value to be found i.e it will ignore all values smaller than the value to be found. But, when we define a comparator same as defined in the lecture, the lower bound function ignores all the value smaller than or equal to the value to be found and hence will always return the index of key which has value greater than the value to be found. Hence we will have to subtract 1 from index in order to get the index of key which has value smaller than or equal to the required value.

For eg. arr=[1,2,3,5,7,9,13]
and we need to find lower bound of 5 and 6.
so if we use lower_bound without comparator, we will get ans as value=5 -> index=3 and value=6 -> index=4.
but if we use the comparator as discussed in lecture, we will get ans as value=5 -> index=4 and value=6 -> index=4.
So we will have to subtract 1 in latter case to get index of value smaller than or equal to the value to be found

Hope dis resolves ur doubt

#3

Hi @aayuushh,
I hope ur doubt was resolved. If yes, please mark the doubt as resolved.
Else, if u still have any doubt regarding this question, u can post it here :slight_smile:

#4

I am able to understand what you’re trying to say but the issue is i am able to understand why this comparator function is used to find the element greater than that element but not able to understand how this comparator function works in this case like we have used return a<=b then which comparisons are performed on basis of which our lower bound function gives the larger element

#5

using a<=b, comparator function returns true for all elements <= value to be found. When the comparator function returns false at that time we see that the current index might be the answer. If we dont use comparator function, it returns true only for elements < value to be found.
Since lower bound uses binary search approach internally, it use comparator <= condition in order to search for element greater than value to be found. In the later case lower bound use < condition to find the required index.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.