Implementando upper_bound() y lower_bound() para conjunto ordenado en C++

Prerrequisitos: Conjunto ordenado y GNU C++ PBDS 
Dado un conjunto ordenado y una clave K , la tarea es encontrar el límite superior y el límite inferior del elemento K en el conjunto en C++. Si el elemento no está presente o no se pudo calcular ninguno de los límites, imprima -1 .
 

El conjunto ordenado es una estructura de datos basada en políticas en g ++ que mantiene los elementos únicos en orden. Realiza todas las operaciones realizadas por la estructura de datos establecida en STL en complejidad log(n). Aparte de eso, realiza dos operaciones adicionales también en complejidad log(n) como: 
1. order_of_key (K): Número de elementos estrictamente más pequeños que K. 
2. find_by_order(K): K ^-ésimo elemento en un conjunto (contando desde cero ). 
 

Ejemplos: 

Entrada: set[] = {10, 20, 30, 40, 50, 60}, K = 30 
Salida: 
Límite inferior de 30: 30 
Límite superior de 30: 40 
Explicación: 
El límite inferior para el elemento 30 es 30 ubicado en la posición 2 
El límite superior para el elemento 30 es 40 ubicado en la posición 3
Entrada: set[] = {10, 20, 30, 40, 50, 60}, K = 60 
Salida: 
Límite inferior de 60: 5
Límite superior de 60: – 1 

Acercarse: 

• upper_bound(): La función upper_bound(clave) devuelve el elemento que es mayor que la clave pasada en el parámetro.
• lower_bound(): La función lower_bound(key) devuelve el elemento que es equivalente a la clave pasada en el parámetro. Si la clave no está presente en el conjunto ordenado, entonces la función debe devolver el elemento que es mayor que el parámetro.
• Para implementar las funciones upper_bound y lower_bound, el índice del elemento, si está presente en el conjunto ordenado pasado como parámetro, se encuentra usando la función order_of_key() .
• Ahora, tanto el límite inferior como el límite superior se pueden encontrar simplemente comparando los elementos presentes en este índice.

A continuación se muestra la implementación de lower_bound() y upper_bound():

// C++ program to implement the
// lower_bound() and upper_bound()
// using Ordered Set
 
#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 set1;
 
// Function that returns the lower bound
// of the element
int lower_bound(int x)
{
    // Finding the position of the element
    int pos = set1.order_of_key(x);
 
    // If the element is not present in the set
    if (pos == set1.size())
    {
        return -1;
    }
 
    // Finding the element at the position
    else
    {
        int element = *(set1.find_by_order(pos));
 
        return element;
    }
}
 
// Function that returns the upper bound
// of the element
int upper_bound(int x)
{
    // Finding the position of the element
    int pos = set1.order_of_key(x + 1);
 
    // If the element is not present
    if (pos == set1.size())
    {
        return -1;
    }
 
    // Finding the element at the position
    else
    {
        int element = *(set1.find_by_order(pos));
 
        return element;
    }
}
 
// Function to print Upper
// and Lower bound of K
// in Ordered Set
void printBound(int K)
{
 
    cout << "Lower Bound of " << K << ": " << lower_bound(K)
         << endl;
    cout << "Upper Bound of " << K << ": " << upper_bound(K)
         << endl;
}
 
// Driver's Code
int main()
{
    set1.insert(10);
    set1.insert(20);
    set1.insert(30);
    set1.insert(40);
    set1.insert(50);
 
    int K = 30;
    printBound(K);
 
    K = 60;
    printBound(K);
 
    return 0;
}

Lower Bound of 30: 30
Upper Bound of 30: 40
Lower Bound of 60: -1
Upper Bound of 60: -1

Complejidad de tiempo: O (log N)