according to the compare function we passed the and should be the value less that or equal to 168 i.e 100 but still it return 200 if we don’t do -1, why?
shouldn’t it return address of element 100 without -1?
Why we did lower_bound()-coins-1
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.
1 Like
then can’t we use simply upper_bound then?
Am i wrong somewhere? or am i not clear at my point?
Yes you can use upper bound here. Sir did it using lower bound here as he had to discuss about using comaparators with lower bound function.
one last doubt, if you could help me understand the following code https://ide.codingblocks.com/s/260546. Here when i want to do lower bound as shown in video and according to what you explained above, a<=b in this if its true it will continue to run and it will stop when a>b happens. I tried printing a,b whenever comparator runs.
at first it is 50 and 168 okay 50 is less it will run again
sencond its 500 and 168 here a>b happens tthen why isn’t it returning 500 index?
even after this its still runnnig till it encounters 100 and then it stops and retrurn address of 200
See this is actually a binary search.
First comparison is done with the mid element which is 50. Since 168 is >50. Now search compresses to the right half. It now compares with 500. Since 168<500. The search will now compress to left subpart and so on…
You can also go through this discussion to understand how comparator is working Sir why we are putting -1 even after applying compare
In comparator <= is used… it means it will reject all values <= to searched value. So simple answer will converge to the first value > the searched value.
1 Like
ohh, okay thanks got it.
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.