Implement upper_bound() and lower_bound() in Ordered Set in 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)

Leave a Reply

Your email address will not be published. Required fields are marked *