std::binary_search — cppreference.com

De cppreference.com

Déclaré dans l'en-tête `<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)

Vérifie si le [first, last) gamme triée contient un élément égal à value. La première version utilise operator< de comparer les éléments, la deuxième version utilise la fonction de comparaison donnée 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.

Paramètres

first, last	-	l'éventail des éléments à examiner 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	-	valeur à comparer les éléments d' 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`.

Retourne la valeur

true si un élément égal à value se trouve, false autrement .

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.

Complexité

Logarithmique de la distance entre first et 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.

Mise en œuvre possible

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));
}

Exemple

#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";
        }
    }
}

Résultat :

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

Voir aussi


	rendements varient d'éléments correspondant à une clé spécifique 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. (fonction générique) [edit]