Lower bound in C++ STL

For Arrays, Vectors, Sets, and Maps.

Table of contents

· Overview
· lower bound
∘ lower bound in an entire array
∘ lower bound in a subarray
∘ lower bound in an entire vector
∘ lower bound in a sub-vector
∘ lower bound in a set
∘ lower bound in a map

Overview

Understanding lower and upper bounds is crucial for efficient coding and most importantly in competitive programming. These bounds define the range within which certain operations can be performed. It allows efficient search within arrays, vectors, sets, and maps.

In this article, we’ll explore the significance of lower bounds, their relation to data structures, and how they can be effectively utilized using C++’s Standard Template Library (STL).

lower bound

To access the lower bound function and other related functions, it’s necessary to include the header file in your C++ code.

It’s important to note that in order to correctly find the lower bound, the data structure must be sorted

lower bound returns pointer/iterator to the first occurrence of the element which is no less than i.e. greater or equal to the value mentioned.

If no such element exists then, it returns the pointer/iterator to the end of data structure.

Syntax:

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val)

Time complexity:

O(log(n)) where n is the length of the data structure.

Enough with the theory; now let’s dive into the practical implementation of lower bound in code. In this article, we will explore how to use the lower bound function in various data structures such as arrays, vectors, sets, and maps.

lower bound in an entire array

int main() 
{
    int n = 8;
    int arr[] = {15, 20, 20, 25, 30, 35, 40, 45};
    
    int arrLowerBoundToFind[] = {11, 20, 17, 80};
    int nToFind = 4;

    for(int i = 0; i < nToFind; i++)
    {
        int *ptr = lower_bound(arr, arr + n, arrLowerBoundToFind[i]);
        if(ptr-arr == n)
        {
            cout<<i+1<<") For "<<arrLowerBoundToFind[i]<<", lower bound is "<<*ptr<<" at index "<<ptr-arr<<", hence the lower bound doesn't exist in given subarray\n";
        }
        else
        {
            cout<<i+1<<") For "<<arrLowerBoundToFind[i]<<", lower bound is "<<*ptr<<" at index "<<ptr-arr<<"\n";
        }
    }
    
    return 0;
}

Output:
1) For 11, lower bound is 15 at index 0
2) For 20, lower bound is 20 at index 1
3) For 17, lower bound is 20 at index 1
4) For 80, lower bound is 4199824 at index 8, hence the lower bound doesn't exist in given subarray

Here, in the output, as you can see, we observe the following:

1. value 11 doesn’t exist hence pointer to 15 is returned since it’s next greater than 11.
2. value 20 has two occurrences so the pointer at first occurrence is returned.
3. value 17 also doesn’t exist but next greater value i.e. 20 has two occurrences so first occurrence of value 20 is returned.
4. In cases where the value we are searching for, such as 80, does not exist in the data structure, the lower bound function returns a pointer to the immediate next element. In this scenario, the pointer points to index 8, but it may contain some garbage value like 4199824.

lower bound in a subarray

int main()  
{
    int n = 5; //length of subarray
    int arr[] = {15, 20, 20, 25, 30, 35, 40, 45};
    
    int arrLowerBoundToFind[] = {11, 20, 17, 80};
    int nToFind = 4;

    for(int i = 0; i < nToFind; i++)
    {
        int *ptr = lower_bound(arr, arr + n, arrLowerBoundToFind[i]);
        
        if(ptr-arr == n)
        {
            cout<<i+1<<") For "<<arrLowerBoundToFind[i]<<", lower bound is "<<*ptr<<" at index "<<ptr-arr<<", hence the lower bound doesn't exist in given subarray\n";
        }
        else
        {
            cout<<i+1<<") For "<<arrLowerBoundToFind[i]<<", lower bound is "<<*ptr<<" at index "<<ptr-arr<<"\n";
        }
    }
    
    return 0;
}

Output
1) For 11, lower bound is 15 at index 0
2) For 20, lower bound is 20 at index 1
3) For 17, lower bound is 20 at index 1
4) For 80, lower bound is 35 at index 5, hence the lower bound doesn't exist in given subarray

here, the output for value 11, 20, 17 is same as the first example.

It’s worth noting that for the value 80, our code has printed index 5 instead of index 8, as in the first example. This difference arises because we have passed a pointer to the subarray until index 5. Consequently, the lower bound search is performed within the subarray from index 0 to 4. It’s crucial to consider the range of the subarray correctly when applying the lower bound function to ensure accurate results.

Now, value 80 is not present in given subarray, so pointer to the immediate next element in subarray is returned i.e. index 5 with value 35.

lower bound in an entire vector

int main() 
{
    vector<int> v = {15, 20, 20, 25, 30, 35, 40, 45};
    vector<int> vLowerBoundToFind = {11, 20, 17, 80};
    
    for(int i = 0; i < vLowerBoundToFind.size(); i++)
    {
        vector<int>::iterator itr = lower_bound(v.begin(), v.end(), vLowerBoundToFind[i]);
        
        if(itr == v.end())
        {
            cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<*itr<<" at index "<<itr-v.begin()<<", hence the lower bound doesn't exist in given vector\n";
        }
        else
        {
            cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<*itr<<" at index "<<itr-v.begin()<<"\n";   
        }
    }
    return 0;
}

output:
1) For 11, lower bound is 15 at index 0
2) For 20, lower bound is 20 at index 1
3) For 17, lower bound is 20 at index 1
4) For 80, lower bound is 0 at index 8, hence the lower bound doesn't exist in given vector

lower bound in a sub-vector

int main() 
{
    vector<int> v = {15, 20, 20, 25, 30, 35, 40, 45};
    vector<int> vLowerBoundToFind = {11, 20, 17, 80};
    
    for(int i = 0; i < vLowerBoundToFind.size(); i++)
    {
        vector<int>::iterator itr = lower_bound(v.begin(), v.begin() + 5, vLowerBoundToFind[i]);
        
        if(itr == v.begin() + 5)
        {
            cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<*itr<<" at index "<<itr-v.begin()<<", hence the lower bound doesn't exist in given subvector\n";
        }
        else
        {
            cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<*itr<<" at index "<<itr-v.begin()<<"\n";
        }
    }
    return 0;
}

output:
1) For 11, lower bound is 15 at index 0
2) For 20, lower bound is 20 at index 1
3) For 17, lower bound is 20 at index 1
4) For 80, lower bound is 35 at index 5, hence the lower bound doesn't exist in given subvector

here, we can see, provided the same input values, the output is exactly same as arrays.

The code of finding lower bound in a array and vector is similar. The only difference is, pointers has to be mentioned and returned in case of arrays, and iterators has to be mentioned and returned in case of vectors.

lower bound in a set

The syntax for finding the lower bound in a set is different from that of arrays and vectors. The set class in C++ has its own implementation of the lower bound function

If the value exceeds the maximum value in set, then the iterator returned is equivalent to setName.end().

int main() 
{
    set<int> s= {15, 20, 20, 25, 30, 35, 40, 45};
    vector<int> vLowerBoundToFind = {11, 20, 17, 80};
    
    for(int i = 0; i < vLowerBoundToFind.size(); i++)
    {
        set<int>::iterator itr = s.lower_bound(vLowerBoundToFind[i]); 
        if(itr == s.end())
        {
            cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<*itr<<", hence the lower bound doesn't exist\n";
        }
        else
        {
            cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<*itr<<"\n";
        }
        
    }
    
    return 0;
}

1) For 11, lower bound is 15
2) For 20, lower bound is 20
3) For 17, lower bound is 20
4) For 80, lower bound is 7, hence the lower bound doesn't exist

here as well, for value 11, 20, 17 the lower bound is same as above examples. However, for the value 80, a garbage value of 7 is printed, which is stored at the location pointed to by the iterator s.end().

lower bound in a map

When working with a map, the lower bound function considers the keys to determine the bounds. The lower bound in a map represents the iterator pointing to the first element whose key is not less than the searched value. This distinction is crucial because maps are key-value pair containers.

If the value exceeds the maximum value in map, then the iterator returned is equivalent to mapName.end().

int main() 
{
    map<int, int> m;
    m.insert({15, 1});
    m.insert({20, 1});
    m.insert({20, 1});
    m.insert({25, 1});
    m.insert({30, 1});
    m.insert({35, 1});
    m.insert({40, 1});
    m.insert({45, 1});
    
    vector<int> vLowerBoundToFind = {11, 20, 17, 80};
    
    for(int i = 0; i < vLowerBoundToFind.size(); i++)
    {
        auto itr = m.lower_bound(vLowerBoundToFind[i]);
        
        if(itr == m.end())
        {
           cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<(*itr).first<<", "<<(*itr).second<<", hence the lower bound doesn't exist\n"; 
        }
        else
        {
            cout<<i+1<<") For "<<vLowerBoundToFind[i]<<", lower bound is "<<(*itr).first<<", "<<(*itr).second<<"\n";
        }
    }
    
    return 0;
}

1) For 11, lower bound is 15, 1
2) For 20, lower bound is 20, 1
3) For 17, lower bound is 20, 1
4) For 80, lower bound is 7, 0, hence the lower bound doesn't exist

here, lower bounds are found according to the keys of the map, but the logic remains the same. i.e. it returns iterator to the key which is no less than i.e. greater or equal to the value mentioned as last argument.

In conclusion, By utilizing lower bound function, you can easily locate the first element that is not less than a specified value within a sorted range. Remember to handle edge cases and situations where the lower bound is not found, ensuring your code is robust and error-resistant.