Please read the new rule regarding the restriction on the use of AI tools. ×

CantLoseNow's blog

some confusion regarding lower bound and upperbound for non increasing vectors...
By CantLoseNow, history, 23 months ago, In English

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...

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 it

I'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?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

auto it = lower_bound(v.begin(), v.end(), who_to_compare);

How do you think lower_bound's code must know that v is sorted non-increasing?
Answer: lower_bound doesn't know it. By default there is assuming that v sorted non-decreasing.
What you must do? Pass greater<int>{} as fourth argument to lower_bound. Logic there absolutely the same as in sort. Code uses < operation in both methods, so you must say, what correct < operation is.

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I really didn't get it...do you mean lowerbound wants the vector to be sorted in non-decreasing order?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not exactly, lower_bound wants v to be sorted by some compare object. By default it is std::less (meaning a < b => [ind of a] < [ind of b]).

      You pass std::greater as fourth argument, and now lower_bound think that a > b => [ind of a] < [ind of b].

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yep

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              23 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              set/multiset keep info about how items are sorted in itselfs. So lower_bound/upper_bound accept only key to find

              set<int, greater<int>> s;
s.insert(2);
s.insert(3);
s.insert(6);
auto it = s.lower_bound(5); // returns iterator to 3
              → Reply