Implementación de lower_bound() y upper_bound() en Array of Pairs en C++

En este artículo discutiremos la implementación de lower_bound() y upper_bound() en una array de pares .

• lower_bound(): Devuelve un iterador que apunta al primer elemento del rango [first, last) que tiene un valor mayor o igual al valor dado “val” . Pero en Array of Pairs lower_bound() for pair(x, y) devolverá un iterador que apunta a la posición del par cuyo primer valor es mayor o igual a x y el segundo valor es mayor que igual a y .
  Si no se cumplen los criterios mencionados anteriormente, devuelve un iterador al índice que está fuera de la array de pares.
• upper_bound(): Devuelve un iterador que apunta al primer elemento del rango [first, last) que tiene un valor mayor que el valor dado “val” . Pero en Array of Pairs upper_bound() for pair(x, y) devolverá un iterador que apunta a la posición del par cuyo primer valor es mayor que x y el segundo valor es mayor que y .
  Si no se cumplen los criterios mencionados anteriormente, devuelve un iterador al índice que está fuera de la array de pares.

Sintaxis:

// Para el límite inferior
lower_bound(array_name, array_name + array_size, value, comparador_function);

// Para el límite superior
upper_bound(array_name, array_name + array_size, value, comparador_function);

Parámetros: La función lower_bound() y upper_bound() en una array de pares acepta los siguientes parámetros:

1. array_name & array_size: El nombre y el tamaño de la array que representa el intervalo entre [start, end) .
2. value: Valor de lower_bound()/upper_bound() a buscar en el rango.
3. función_comparador: Función binaria que acepta dos argumentos como su entrada, a saber, un elemento de tipo par de la array, y el segundo es el valor para el cual se debe encontrar lower_bound()/upper_bound() y devuelve un valor booleano.

Tipo de retorno: Devuelve un iterador que apunta al primer elemento del arreglo cuyo primer parámetro es mayor o igual que el valor.

A continuación se muestra el programa para demostrar lower_bound() y upper_bound() en una array de pares:

// C++ program to demonstrate lower_bound()
// and upper_bound() in Array of Pairs
#include <bits/stdc++.h>
using namespace std;
  
// Function to implement lower_bound()
void findLowerBound(pair<int, int> arr[],
                    pair<int, int>& p,
                    int n)
{
    // Given iterator points to the
    // lower_bound() of given pair
    auto low = lower_bound(arr, arr + n, p);
  
    cout << "lower_bound() for {2, 5}"
         << " is at index: "
         << low - arr << endl;
}
  
// Function to implement upper_bound()
void findUpperBound(pair<int, int> arr[],
                    pair<int, int>& p,
                    int n)
{
    // Given iterator points to the
    // lower_bound() of given pair
    auto up = upper_bound(arr, arr + n, p);
  
    cout << "upper_bound() for {2, 5}"
         << " is at index: "
         << up - arr << endl;
}
  
// Driver Code
int main()
{
    // Given sorted array of Pairs
    pair<int, int> arr[]
        = { { 1, 3 }, { 1, 7 }, { 2, 4 },
            { 2, 5 }, { 3, 8 }, { 8, 6 } };
  
    // Given pair {2, 5}
    pair<int, int> p = { 2, 5 };
  
    // Size of array
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Function Call to find lower_bound
    // of pair p in arr
    findLowerBound(arr, p, n);
  
    // Function Call to find upper_bound
    // of pair p in arr
    findUpperBound(arr, p, n);
    return 0;
}

lower_bound() for {2, 5} is at index: 3
upper_bound() for {2, 5} is at index: 4