Implement upper_bound() and lower_bound() in Ordered Set in C++

By Prabhnoor Singh

We will learn about std::upper_bound and std::lower_bound functions.

lower_bound()

lower_bound() is an inbuilt function in C++. It is used to return an iterator pointer to the key from the set. This function is applied to an ordered set. It takes a parameter (value to be searched in the set) and returns a value equivalent to the passed parameter. If an equivalent value is not present in the set then the next value, just greater than the given parameter is returned. And if there is no just greater value in the set container then it returns set::end().In case if any exception is thrown then set elements don’t change. One can access the set container elements concurrently, there is no harm to the set. Time complexity is O(log(n)).

Example 1

#include<iostream>
#include<set>
using namespace std;

int main()
{
    set<int> num = {11, 13, 14, 15, 16, 17, 18};
    int k1 = 11, k2 = 12;
    auto a = num.lower_bound(k1);
    auto b = num.lower_bound(k2);
    cout << "Lower bound of " << k1 << " is " << *a << endl;
    cout << "Lower bound of " << k2 << " is " << *b << endl;
    return 0;
}

Output :Lower bound of 11 is 11
Lower bound of 12 is 13

In the above example, we can notice for the lower bound of ’11’ function returned ’11’, which is present in the set. And for the lower bound of ’12’, since element equivalent ’12’ is not present in the container set then just a greater than ’12’ value is returned. If no elements are considered to go then std::end is returned.

Example 2

#include<iostream>
#include<set>
using namespace std;

int main()
{
    set<char> letters = {'a','b','c','d','e'};
   auto ch = letters.lower_bound('c');
    cout << "Lower bound : " << *ch << endl;
    return 0;
}

Output :Lower bound : c

#include<iostream>
#include<set>
using namespace std;

int main()
{
    set<int> num = {11, 13, 14, 15, 16, 17, 18};
    int k1 = 11, k2 = 12;
    auto a = num.upper_bound(k1);
    auto b = num.upper_bound(k2);
    cout << "Lower bound of " << k1 << " is " << *a << endl;
    cout << "Lower bound of " << k2 << " is " << *b << endl;
    return 0;
}

Output :Lower bound of 11 is 13
Lower bound of 12 is 13

#include<iostream>
#include<set>
using namespace std;

int main()
{
    set<char> letters = {'a','b','c','d','e'};
   auto ch = letters.upper_bound('c');
    cout << "Lower bound : " << *ch << endl;
    return 0;
}

Output :
Upper bound : c

For a sorted set and a key, print the lower bound and the upper bound of the key K in the set in C++ or print -1 if the element is not present or out of bounds. First, we need to know what an ordered set is.

What is an ordered set?

An ordered set is a policy-based data structure just like the set data structure in STL which has unique elements in sorted order. It carries out all functions performed by the set class in log(n) time complexity and two more additional functions also in log(n) complexity. These are:-

• order_of_key(k):  Number of elements strictly smaller than k.
• find_by_order(k): K-th element in a set (counting from zero).

To use ordered_set and GNU C++ library contains other policy data structures, there are headers we need to include:

• #include<ext/pb_ds/assoc_container.hpp>
• #include<ext/pb_ds/tree_policy.hpp>

Upper_bound() and lower_bound()

upper_bound(): The function upper_bound(key) returns the element which is just greater than key.

lower_bound(): The function lower_bound(key)  returns the element which is equal to the key.

Examples:-

Input:

s[]={1,2,3,4,5}, K=3

Output:
Lower Bound: 3
Upper Bound: 4

Input:

s[]={1,2,3,4,5,6}

Output:
Lower Bound: -1
Upper Bound: -1

The approach toward the problem

With the help of the order_of_key() function, we first find if the element’s index is present in the given ordered set. Now by simply comparing the element at this index, we can find both the lower bound and the upper bound.

C++ Program to implement lower_bound() and upper_bound()

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

// ordered set tree
typedef tree<int, null_type,
             less<int>,
             rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

ordered_set s1;


// function returning lower bound of key
int l_bound(int x)
{
    // finding the position of element
    int p=s1.order_of_key(x);

    // if element not present
    if(p==s1.size()) return -1;

    //finding element's position
    else
    {
        int e=*(s1.find_by_order(p));
        return e;
    }
}
int u_bound(int x)
{
    // finding the position of element
    int p=s1.order_of_key(x+1);

    // if element not present
    if(p==s1.size()) return -1;

    //finding element's position
    else
    {
        int e=*(s1.find_by_order(p));
        return e;
    }
}

// print the lower and upper bound
void print(int K)
{
    cout << "Lower Bound of "
         << K << ": "
         << l_bound(K)
         << endl;
    cout << "Upper Bound of "
         << K << ": "
         << u_bound(K)
         << endl;
}

int main()
{
    s1.insert(1);
    s1.insert(2);
    s1.insert(3);
    s1.insert(4);
    s1.insert(5);
    int K=3;
    print(K);
    K=6;
    print(K);
}

Output:

Lower Bound of 3: 3
Upper Bound of 3: 4
Lower Bound of 6: -1
Lower Bound of 6: -1

Time Complexity:

O(log N)