CantLoseNow's blog

some confusion regarding lower bound and upperbound for non increasing vectors...
By CantLoseNow, history, 2 years 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 (7)
| Write comment?
»
2 years 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
  • »
    »
    2 years 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
    • »
      »
      »
      2 years 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
      • »
        »
        »
        »
        2 years 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
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yep

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years 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
            • »
              »
              »
              »
              »
              »
              »
              2 years 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