límite_inferior en C++ – Part 1

Plantillas lower_bound()

: 

Sintaxis 1: 
ForwardIterator lower_bound (ForwardIterator primero, ForwardIterator último, const T& val); 
Sintaxis 2: 
ForwardIterator lower_bound (ForwardIterator primero, ForwardIterator último, const T& val, Compare comp); 
 

Parámetros: Los métodos anteriores aceptan los siguientes parámetros.  

• primero, último: el rango utilizado es [primero, último), que contiene todos los elementos entre primero y último, incluido el elemento señalado por primero pero no el elemento señalado por último.
• val: Valor del límite inferior a buscar en el rango.
• comp: Función binaria que acepta dos argumentos (el primero del tipo apuntado por ForwardIterator, y el segundo, siempre val), y devuelve un valor convertible a bool. La función no modificará ninguno de sus argumentos. Puede ser un puntero de función o un objeto de función.

Valor devuelto: un iterador al límite inferior de val en el rango. Si todos los elementos en el rango se comparan menos que val, la función regresa en último lugar. Si todos los elementos del rango son mayores que val, la función devuelve un puntero al primer elemento. 
Ejemplos: 

Input: 10 20 30 40 50
Output: lower_bound for element 30 at index 2

Input: 10 20 30 40 50
Output: lower_bound for element 35 at index 3

Entrada: 10 20 30 40 50
Salida: límite inferior para el elemento 55 en el índice 5 (básicamente, 55 no está presente, por lo que devuelve el iterador end())

Entrada: 10 20 30 30 30 40 50
Salida: límite inferior para el elemento 30 en el índice 2

// CPP program to illustrate
// std :: lower_bound
#include <bits/stdc++.h>
  
// Driver code
int main()
{
    // Input vector
    std::vector<int> v{ 10, 20, 30, 30, 30, 40, 50 };
  
    // Print vector
    std::cout << "Vector contains :";
    for (unsigned int i = 0; i < v.size(); i++)
        std::cout << " " << v[i];
    std::cout << "\n";
  
    std::vector<int>::iterator low1, low2, low3;
      
    // std :: lower_bound
    low1 = std::lower_bound(v.begin(), v.end(), 30);
    low2 = std::lower_bound(v.begin(), v.end(), 35);
    low3 = std::lower_bound(v.begin(), v.end(), 55);
  
    // Printing the lower bounds
    std::cout
        << "\nlower_bound for element 30 at position : "
        << (low1 - v.begin());
    std::cout
        << "\nlower_bound for element 35 at position : "
        << (low2 - v.begin());
    std::cout
        << "\nlower_bound for element 55 at position : "
        << (low3 - v.begin());
  
    return 0;
}

Vector contains : 10 20 30 30 30 40 50

lower_bound for element 30 at position : 2
lower_bound for element 35 at position : 5
lower_bound for element 55 at position : 7

Complejidad temporal:  el número de comparaciones realizadas es logarítmico. Por lo tanto, la complejidad temporal del enfoque anterior es O(logN) , donde N = tamaño. (último primero)

Este artículo es una contribución de Sachin Bisht , . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.