CPPV03: upper_bound and lower_bound in C++ vectors

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

end() is the iterator object pointing toward index next to the last element i.e for vector of size 8, it points towards 8th index

Quick Summary

• upper_bound returns first element which is > value. If not, return end().
• lower_bound return first element which is ≥ value. If not, return end().

Example

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

Primer on iterators

Iterators are objects in C++ which are used to traverse objects such as lists, sets, vectors and other collections

vector<int>::iterator it = vec.begin();

*vec.end() or *vec.begin() throws a segmentation fault.

Dereferencing vec.end() will result in a segmentation fault because vec.end() points one position beyond the last element of the vector, and attempting to access the value at that position is an undefined behavior and can lead to a segmentation fault.