Why -1 to the value returned by lower_bound()

#1 
 while (x>0)
    {
        auto lb=lower_bound(money,money+n,x,compare)-1;
        cout<<money[lb-money]<<" ";
        x-=money[lb-money];
    }
#2
#3

hello @sagar_aggarwal
we have changed our comparator to make it work like upper bound.
thats why it will always return index of element whose value is greater than the searched key.
and to get the required value , we need to do -1.
Refer to the above code t see the value lower bound is returning .

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.

#4

is there any reference explaining the functunality of lower_bound() and upper_bound() functions internally

#5

yeah u can read the documentation for that.
http://www.cplusplus.com/reference/algorithm/lower_bound/

#6

Hello aman, i have seriously tried to understand that why -1, but i cant understand.

#7

check the comparator of upper bound (from documentation) and the comparator that we designed.

and see are they same or is there any difference

#8

Then why couldn’t we have used upper_bound()-1 instead

#9

the idea behind the video was to teach u how u can design ur own comparator as per ur requirement instead of using defualt one.

#10

According to logic of lower_bound() function i.e it returns An iterator pointing to the first element not less than val, or end() if every element is less than val.
using this comparator function and not using this comparator function should give same output

#include<iostream>
#include<algorithm>
using namespace std;
bool compare(int a,int b)
{
    return a>=b;
}
int main(){
    int money[]={1,2,5,10,20,50,100,200,500,2000};
    int n=sizeof(money)/sizeof(int);
    int x;
    cin>>x;
        auto jk=lower_bound(money,money+n,x);
        auto lb=lower_bound(money,money+n,x,compare);
        cout<<money[lb-money]<<" "<<money[jk-money];
        /* 
        cout<<money[lb-money]<<" ";
        x-=money[lb-money]; */
    
    
    return 0;
}
#11

now whats ur doubt ?

#12

they are not giving same output

#13

check the comparator for lower bound->
image

and the comparator that u have designed.
they r different

#14

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.