Lower bound and upper bound of C++

Lower bound and upper bound in STL

• upper_bound() and lower_bound() are standard library functions in C++.
• upper_bound() returns an iterator pointing to the first element in the range [first, last) that is greater than the value. If no such an element is found, return end().
• lower_bound() returns an iterator pointing to the first element in the range [first, last) which is greater or equal to the value. If no such an element is found, return end().

Quick summary

• upper bound return first element which is > value. If not, return end().
• lower bound return first element which is ≥ value. If not, return end().

Examples

#include <bits/stdc++.h> 
int main() 
{ 
    std::vector<int> v{ 10, 20, 30, 30, 50 }; 
  
    // Print vector 
    std::cout << "Vector contains :"; 
    for (unsigned int i = 0; i < v.size(); i++) 
        std::cout << " " << v[i]; 
    std::cout << "\n"; 
  
    std::vector<int>::iterator low, upp; 
 
    std::cout<<"******* lower_bound *********"<<std::endl;
    low = std::lower_bound(v.begin(), v.end(), 20); 
    std::cout << "\nlower_bound for element 20 at position : " << (low - v.begin()); 
    low = std::lower_bound(v.begin(), v.end(), 25); 
    std::cout << "\nlower_bound for element 25 at position : " << (low - v.begin())<<std::endl; 
    
    
    std::cout<<"****** upper_bound ************"<<std::endl;
    upp = std::upper_bound(v.begin(), v.end(), 30); 
    std::cout << "\nupper_bound for element 30 at position : " << (upp - v.begin()); 
     upp = std::upper_bound(v.begin(), v.end(), 25); 
    std::cout << "\nupper_bound for element 25 at position : " << (upp - v.begin()); 
  
    return 0; 
}

output
Vector contains : 10 20 30 30 50
******* lower_bound *********
lower_bound for element 20 at position : 1
lower_bound for element 25 at position : 2

****** upper_bound ************
upper_bound for element 30 at position : 4
upper_bound for element 25 at position : 2

Examples for set

For set, the logic is the same:

• upper bound return first element which is >value. If not, return end().
• lower bound return first element which is ≥value. If not, return end().

#include <bits/stdc++.h>
using namespace std;
int main(){
   set<int> Set;
   Set.insert(9);
   Set.insert(7);
   Set.insert(5);
   Set.insert(3);
   Set.insert(1);
   cout<<"Elements are : ";
   for (auto i = Set.begin(); i!= Set.end(); i++)
      cout << *i << " ";
   cout<<"******* lower_bound *********"<<endl;
   auto i = Set.lower_bound(5);
   cout <<"\nlower bound of 5 in the set is: ";
   cout << (*i) << endl;
   i = Set.lower_bound(1);
   cout<<"lower bound of 1 in the set is: ";
   cout << (*i) << endl;
     i = Set.lower_bound(4);
   cout<<"lower bound of 4 in the set is: ";
   cout << (*i) << endl;

   cout<<"****** upper_bound ************"<<endl;
   i = Set.upper_bound(5);
   cout <<"\nupper bound of 5 in the set is: ";
   cout << (*i) << endl;
   i = Set.upper_bound(1);
   cout<<"upper bound of 1 in the set is: ";
   cout << (*i) << endl;
   i = Set.upper_bound(4);
   cout<<"upper bound of 4 in the set is: ";
   cout << (*i) << endl;
   
   return 0;
}

Output
Elements are : 1 3 5 7 9 
******* lower_bound *********
lower bound of 5 in the set is: 5
lower bound of 1 in the set is: 1
lower bound of 4 in the set is: 5

****** upper_bound ************
upper bound of 5 in the set is: 7
upper bound of 1 in the set is: 3
upper bound of 4 in the set is: 5

A nice discussion

A nice discussion can be found HERE

upper_bound and lower_bound for non increasing vector in c++

See HERE

Quick summary:

when the vector is sorted reversely
lower_bound return the location of the first element <= value
upper_bound return the location of the first element < value

Thanks for reading.