Why is lower bound of 100 coming out as 100 because I think it should come out as 50 as per this condition?
Please expalin why have we put -1 to find the lower bound?
hello @sahilkhan2312000131
refer this internal implementation for understanding.
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.
Just try in your compiler for different values you will understand
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.
now apply bs serach as per above code. you will find that return index will always be one more than required index
So, Instead of making a comparator, we can simply do this:
int lb1=upper_bound(coins,coins+n,mo1)-coins-1;
int lb2=upper_bound(coins,coins+n,mo2)-coins-1;
yeah , but the idea was to teach u how we can write our own comparator