Lower bound and upper bound of C++

Jimmy (xiaoke) Shen
3 min readFeb 4, 2020

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 : 1lower_bound for element 25 at position : 2
****** upper_bound ************upper_bound for element 30 at position : 4upper_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: 5lower bound of 1 in the set is: 1lower bound of 4 in the set is: 5
****** upper_bound ************upper bound of 5 in the set is: 7upper bound of 1 in the set is: 3upper 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.

--

--