lower_bound

Artigo
06/09/2015

Localiza a posição do primeiro elemento em um intervalo ordenado com um valor que é maior ou equivalente a um valor especificado, onde o critério de ordenação pode ser especificado por um predicado binário.

template<class ForwardIterator, class Type> 
   ForwardIterator lower_bound( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value 
   ); 
template<class ForwardIterator, class Type, class BinaryPredicate> 
   ForwardIterator lower_bound( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value,
      BinaryPredicate comp 
   );

Parâmetros

first
Um iterador de avanço que trata a posição do primeiro elemento no intervalo a ser pesquisado.
last
Um iterador de avanço que trata a posição após o elemento final no intervalo a ser pesquisado.
value
O valor cuja primeira posição ou primeira posição possível está sendo procurado no intervalo ordenado.
comp
Objeto definido pelo usuário de função do predicado em que define o sentido que o elemento é menor do que outros. Um predicado binário leva dois argumentos e retorna true quando satisfeito e false quando não satisfeito.

Valor de retorno

Um iterador de avanço na posição do primeiro elemento em um intervalo ordenado com um valor que é maior ou equivalente a um valor especificado, onde a equivalência é especificada com um predicado binário.

Comentários

O intervalo de origem classificado referenciado deve ser válido; todos os iteradores devem ser diferenciáveis e, na sequência, a última deve ser alcançável a partir da primeira por incrementação.

Um intervalo classificado é uma pré-condição de uso do lower_bound e onde a ordem é a mesmo que a especificado pelo predicado binário.

O intervalo não é modificado pelo algoritmo lower_bound.

Os tipos de valor dos iteradores de encaminhamento precisam ser menor que comparável para serem ordenados, de forma que, considerando dois elementos, pode ser determinado se qualquer um que seja equivalentes (no sentido que nenhum é menor que o outro) ou que um é menor que o outro. Isso resulta em uma ordenação entre os elementos não equivalentes

A complexidade do algoritmo é logarítmica para iteradores de acesso aleatório. Caso contrário, ela é linear, com o número de etapas proporcional a (last – first).

Exemplo

// alg_lower_bound.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // greater<int>( )
#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser( int elem1, int elem2 )
{
    if ( elem1 < 0 )
        elem1 = - elem1;
    if ( elem2 < 0 )
        elem2 = - elem2;
    return elem1 < elem2;
}

int main( )
{
    using namespace std;

    vector<int> v1;
    // Constructing vector v1 with default less-than ordering
    for ( auto i = -1 ; i <= 4 ; ++i )
    {
        v1.push_back(  i );
    }

    for ( auto ii =-3 ; ii <= 0 ; ++ii )
    {
        v1.push_back(  ii  );
    }

    cout << "Starting vector v1 = ( " ;
    for (const auto &Iter : v1)
        cout << Iter << " ";
    cout << ")." << endl;

    sort(v1.begin(), v1.end());
    cout << "Original vector v1 with range sorted by the\n "
        << "binary predicate less than is v1 = ( " ;
    for (const auto &Iter : v1)
        cout << Iter << " ";
    cout << ")." << endl;

    // Constructing vector v2 with range sorted by greater
    vector<int> v2(v1);

    sort(v2.begin(), v2.end(), greater<int>());

    cout << "Original vector v2 with range sorted by the\n "
        << "binary predicate greater is v2 = ( " ;
    for (const auto &Iter : v2)
        cout << Iter << " ";
    cout << ")." << endl;

    // Constructing vectors v3 with range sorted by mod_lesser
    vector<int> v3(v1);
    sort(v3.begin(), v3.end(), mod_lesser);

    cout << "Original vector v3 with range sorted by the\n "
        <<  "binary predicate mod_lesser is v3 = ( " ;
    for (const auto &Iter : v3)
        cout << Iter << " ";
    cout << ")." << endl;

    // Demonstrate lower_bound

    vector<int>::iterator Result;

    // lower_bound of 3 in v1 with default binary predicate less<int>()
    Result = lower_bound(v1.begin(), v1.end(), 3);
    cout << "The lower_bound in v1 for the element with a value of 3 is: "
        << *Result << "." << endl;

    // lower_bound of 3 in v2 with the binary predicate greater<int>( )
    Result = lower_bound(v2.begin(), v2.end(), 3, greater<int>());
    cout << "The lower_bound in v2 for the element with a value of 3 is: "
        << *Result << "." << endl;

    // lower_bound of 3 in v3 with the binary predicate  mod_lesser
    Result = lower_bound(v3.begin(), v3.end(), 3,  mod_lesser);
    cout << "The lower_bound in v3 for the element with a value of 3 is: "
        << *Result << "." << endl;
}

Saída

Starting vector v1 = ( -1 0 1 2 3 4 -3 -2 -1 0 ).
Original vector v1 with range sorted by the
 binary predicate less than is v1 = ( -3 -2 -1 -1 0 0 1 2 3 4 ).
Original vector v2 with range sorted by the
 binary predicate greater is v2 = ( 4 3 2 1 0 0 -1 -1 -2 -3 ).
Original vector v3 with range sorted by the
 binary predicate mod_lesser is v3 = ( 0 0 -1 -1 1 -2 2 -3 3 4 ).
The lower_bound in v1 for the element with a value of 3 is: 3.
The lower_bound in v2 for the element with a value of 3 is: 3.
The lower_bound in v3 for the element with a value of 3 is: -3.