Money problem using lower bound function

#1

In line no 15 , why are we subtracting 1? since we have defined the LB as it will return the address of element less than or equal to key. so simply subtracting lb-coins should give the result na?

#2

Hello @nilotpal
As we have changed our comparator function so that it works like upper bound. So it will always return index of that element whose value is greater than the needed value and to get the required value , we need to do -1.
Suppose, 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.
By 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.

#3

In lecture sir is saying that by defining comprator a<=b, we will return a value which is less than or equal to key(money); that means by simply subtracting LB-coins should give the index na?

#4

In this code, we have defined the comprator , so for 120, it should return a value less than or equal to 120 i.e. 100 na, but its returning 200

#5

@nilotpal 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.
at this point we have to do -1 in the index.

#6
#7

this is because when our comparator will stop it will be at 200 so that s why we have to subtract 1 from that.

1 Like