so i know how lowerbound and upperbound works for a vector sorted in ascending order. But what if i arrange the vector in descending order? i wanted to know the answer and i searched it on cppreference but i was not able to understand it there. so i also wrote a small code to test it out. According to the definition of lower bound in geeksforgeeks —
"The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val."
so if i wrote a code like this:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int who_to_compare;
cin >> who_to_compare;
vector<int> v;
for(int i=0;i<n;i++){
int temp;
cin >> temp;
v.push_back(temp);
}
sort(v.begin(), v.end(), greater<int>());
auto it = lower_bound(v.begin(), v.end(), who_to_compare);
cout << v[it-v.begin()];
}
and my input is : 5 4 5 3 7 8 5
then the output is : 8
-> which is like correct according to me since 8 is the first number which is greater than 4 and is the first number in the range to be greater than 4 .(idk if i am correct, pls correct me here).
but when my input is : 5 6 5 3 7 8 5
then the output is : 0
-> why is it so ? shouldn't it be 8? because 8 is the first element in the range to be greater than 6.
Please help me understand this whole thing better...
first and foremost, you can replace
v[it-v.begin()]
with*it
also your post is not clear, i don't understand what's the
who_to_compare
value here,Here's what the vector's gonna look like after it's sorted:
8 7 5 5 5 4 3
lower_bound and upper_bound does not find the first element that's equal or greater than the value which is being compared to, rather a value that exists in the element thats equal or larger to the element (or larget if upper_bound), if it does not exist, it returns v.end(), so it is not guaranteed to return the first element that's equal or larger (lower_bound) or larger (upper_bound) than the value given to itI'm still not really sure why it'd return zero since it is not in the array, are you sure you're printing the number rather than the index?
auto it = lower_bound(v.begin(), v.end(), who_to_compare);
How do you think
lower_bound
's code must know thatv
is sorted non-increasing?Answer:
lower_bound
doesn't know it. By default there is assuming thatv
sorted non-decreasing.What you must do? Pass
greater<int>{}
as fourth argument tolower_bound
. Logic there absolutely the same as insort
. Code uses<
operation in both methods, so you must say, what correct<
operation is.I really didn't get it...do you mean lowerbound wants the vector to be sorted in non-decreasing order?
Not exactly,
lower_bound
wantsv
to be sorted by some compare object. By default it isstd::less
(meaninga < b => [ind of a] < [ind of b]
).You pass
std::greater
as fourth argument, and nowlower_bound
think thata > b => [ind of a] < [ind of b]
.so if my vector is in non increasing order, then i have to pass greater{} as the 4th argument. basically however my vector is sorted, i need to pass that same comparison to lowerbound as 4th argument right?
Yep
also is it the same in other data structures? like if i make a multiset<int,greater > s. then i use multiset::lowerbound, will it be correct? or do i have to pass greater in lowerbound there also?
set/multiset keep info about how items are sorted in itselfs. So
lower_bound
/upper_bound
accept only key to find