std::upper_bound

Encontra o primeiro elemento maior que um valor em um intervalo ordenado [first, last) usando busca binária.

  • Cabeçalho: <algorithm>
  • Assinatura:
upper_bound(ForwardIt first, ForwardIt last, const T& value);
upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);
  • Parâmetros:
    • first, last - Iteradores que definem o intervalo ordenado de busca.
    • value - Valor de referência para a busca.
    • comp - Função de comparação que retorna true se o primeiro elemento for menor que o segundo (padrão: std::less).
  • Retorno: Iterador para o primeiro elemento maior que value ou last se não encontrado.
  • Exceções: Nenhuma, a menos que a função de comparação comp lance.
  • Versão: C++98
  • Performance: O(log N), onde N é o número de elementos no intervalo.
  • Exemplo:
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5};
    auto it = std::upper_bound(vec.begin(), vec.end(), 2); // Aponta para o primeiro 4
    if (it != vec.end()) std::cout << *it << '\n'; // Imprime: 4
    // Com comparação personalizada
    auto comp = [](int a, int b) { return a > b; };
    std::vector<int> vec_desc = {5, 4, 4, 2, 1};
    it = std::upper_bound(vec_desc.begin(), vec_desc.end(), 4, comp); // Aponta para o primeiro 2
    if (it != vec_desc.end()) std::cout << *it << '\n'; // Imprime: 2
    return 0;
}