std::binary_search - cppreference.com

De cppreference.com

Definido no cabeçalho `<algorithm>`

`template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );`	(1)

`template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );`	(2)

Verifica se o [first, last) intervalo classificado contém um elemento igual a value. A primeira versão utiliza operator< para comparar os elementos, a segunda versão utiliza a função de comparação dada comp.

Original:

Checks if the sorted range [first, last) contains an element equal to value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Parâmetros

first, last	-	a gama de elementos para examinar Original: the range of elements to examine The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
value	-	valor a comparar os elementos de Original: value to compare the elements to The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
comp	-	comparison function which returns `true` if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: `bool cmp(const Type1 &a, const Type2 &b);` The signature does not need to have `const &`, but the function must not modify the objects passed to it. The type `Type1` must be such that an object of type `T` can be implicitly converted to `Type1`. The type `Type2` must be such that an object of type `ForwardIt` can be dereferenced and then implicitly converted to `Type2`.
Type requirements
-`ForwardIt` must meet the requirements of `ForwardIterator`.

Valor de retorno

true se um elemento igual a value é encontrada, de outro modo.. false

Original:

true if an element equal to value is found, false otherwise.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Complexidade

Logarítmica na distância entre first e last

Original:

Logarithmic in the distance between first and last

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Possível implementação

First version
template<class ForwardIt, class T> bool binary_search(ForwardIt first, ForwardIt last, const T& value) { first = std::lower_bound(first, last, value); return (first != last && !(value < *first)); }
Second version
template<class ForwardIt, class T, class Compare> bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp) { first = std::lower_bound(first, last, value); return (first != last && !(comp(value, *first)); }

First version

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (first != last && !(value < *first));
}

Second version

template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value);
    return (first != last && !(comp(value, *first));
}

Exemplo

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> haystack {1, 3, 4, 5, 9};
    std::vector<int> needles {1, 2, 3};

    for (auto needle : needles) {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
            std::cout << "Found " << needle << '\n';
        } else {
            std::cout << "no dice!\n";
        }
    }
}

Saída:

Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3

Veja também


	retorna a escala de elementos que combinam com uma tecla específica Original: returns range of elements matching a specific key The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (modelo de função) [edit]