Regarding the cpmparators

#1

in the video
int lb=lower_bound(coins , coins +n ,money ,compare)-coins-1
why we have done -1

#2

Check the custom lower bound function here https://ide.codingblocks.com/s/197380
It returns an iterator always pointing a step ahead of desired result. That is why -1 is done.
Say you have 120 Rs…your custom lower bound will return iterator to 200
Even for Rs 100,your custom lower bound will return 200.
This is why -1 is done…so that it satisfies all case…

#3

but we changed the lower bound function to <= which means for 120 it should return 100 which is fine

#4

Hi @aslesha.j7,
if we use lower_bound without comparator, it returns a value which is >= req. value.
But, using our own comparator, we return a value which is greater than req. value. In, comparator, we use <= i.e it will return value which is > the req. value.
So, thats why -1 is done.
Hope dis resolves ur doubt.

#5

In, comparator, we use <= i.e it will return value which is just lower or equal to the reqd value as said by sir in the video

#6

in the video, sir said that the lower bound function without comparator gives a value which is >= req. value.
So,he meant that we need a comparator to get a value > req. value i.e use the comparator (we made) to get a value > req. value.So, using comparator without subtracting 1 we get a value > req. value. U can try urself that if we dont use -1, we will get a value which is greater than req. value.
Also, the lower bound function without comparator uses < comparision to find the value. So, its find a value just >= req. value. Now, using comparator we use <= comparision to get a value just > req. value.
Hope dis clears ur doubt.

#7

Im still not able to understand whats happening. can you send me a dry run of how both compare and lower_bound functions are working

#8

plz reply to my ques

#9

Below, i hv tried to explain using binary search function.

CASE1-Without Comparator:
array={1,2,3,4,5};ans=-1; required value=1, lower bound function uses binary search with < comparision to find the value >= req. value.
start=0,end=4,mid=2--------since array[mid]=3>= req. value----------so make end=2,ans=2
start=0,end=2,mid=1--------since array[mid]=2>= req. value----------so make end=1,ans=1,
start=0,end=1,mid=0--------since array[mid]=1>= req. value-----------so make end=0,ans=0
start=0,end=0,mid=1---------since array[mid]=1< req. value------------so make start=1
since start is now >high, we exit binary search and function returns ans=0.

CASE2-With Comparator
array={1,2,3,4,5};required value=1,lower bound function uses binary search with <= comparision to find the value > req. value.
start=0,end=4,mid=2--------since array[mid]=3> req. value-----------so make end=2,ans=2
start=0,end=2,mid=1--------since array[mid]=2> req. value-----------so make end=1,ans=1,
start=0,end=1,mid=0--------since array[mid]=1<= req. value-----------so make start=1
start=1,end=1,mid=1---------since array[mid]=2> req. value------------so make end=0,ans=1
since start is now >high, we exit binary search and function returns ans=1.

Hope this clears ur doubt.

1 Like
#10

Im trying very hard to understand the concept but cant figure out. Thanks for helping.

1 Like
#11

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.