Neste artigo, discutiremos a implementação de lower_bound() e upper_bound() em uma array de pares .

• lower_bound(): retorna um iterador apontando para o primeiro elemento no intervalo [primeiro, último) que possui um valor maior ou igual ao valor dado “val” . Mas em Array of Pairs lower_bound() para pair (x, y) retornará um iterador apontando para a posição do par cujo primeiro valor é maior ou igual a xe o segundo valor é maior que igual a y .
  Se os critérios mencionados acima não forem atendidos, ele retorna um iterador para o índice que sai da array de pares.
• upper_bound(): retorna um iterador apontando para o primeiro elemento no intervalo [primeiro, último) que possui um valor maior do que o valor “val” fornecido . Mas em Array of Pairs upper_bound() para pair (x, y) retornará um iterador apontando para a posição do par cujo primeiro valor é maior que xe o segundo valor é maior que y .
  Se os critérios mencionados acima não forem atendidos, ele retorna um iterador para o índice que sai da array de pares.

Sintaxe:

// Para limite inferior
limite_inferior (array_name, array_name + array_size, value, comparator_function);

// Para limite superior
limite_maior (array_name, array_name + array_size, value, comparator_function);

Parâmetros: a função lower_bound() e upper_bound() em uma array de pares aceita os seguintes parâmetros:

1. array_name e array_size: O nome e tamanho do array que representa o intervalo entre [início, fim) .
2. valor: valor de lower_bound() / upper_bound() a ser pesquisado no intervalo.
3. comparator_function: função binária que aceita dois argumentos como sua entrada, a saber, um elemento do par de tipos do array, e o segundo é o valor para o qual lower_bound() / upper_bound() deve ser encontrado e retorna um valor booleano.

Tipo de retorno: retorna um iterador apontando para o primeiro elemento da array cujo primeiro parâmetro é maior ou igual ao valor.

Abaixo está o programa para demonstrar lower_bound() e upper_bound() em uma 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() para {2, 5} está no índice: 3
upper_bound() para {2, 5} está no índice: 4