In the lower and upper bound video, it was said that lower bound gives us the first element that is greater than equal to the given key.
If we change the code to less than equal to, shouldn’t it give the FIRST element that is less than equal to the given key, why is it giving the last element.
hey @Naman_sood
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.
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.
if this resolves your doubt please mark it resolved
It still should return the FIRST value that is <= in the given comparator function, why does it return the last value. If we see the above list, the function will hold true while comparing 1 and 100/120 so why does it print 100
@Naman_sood
Suggestion:
Re-watch the video, you’ll understand it.its like we are updating the if loop of binary search
The function will return the iterator the required element and subtracting the starting element will give it’s position in the array.
But, to access the element you need to know the index at which it is present.
The relationship between position of element and it’s index in an array/vector is:
index = position -1
Thus, we subtract 1 in the video.
Hope, this would help.
Give a like if you are satisfied.
Hey @Naman_sood
The lower bound function returns the element which is either equal to or greater than the key element(by default). But If we consider the problem, We always want a denomination that is less than or equal to the money(key). So We modified the comparator function and after modification, it returns denomination which is just greater than the amount for 100 and 120 both It will point towards 200 that’s why we subtracted 1, and now in all cases, it will point to the element which is just less than or equal to the money(key) to be calculated i.e. 100 . You can achieve the same using the upper_bound default function and then subtract 1 as usual ,It will serve the same purpose.
Hope this helps