HOWTO · C++
Recherche dichotomique C++ STL
Ce didacticiel montre comment utiliser l'algorithme de Recherche dichotomique de la bibliothèque de modèles standard C++.
C++ nous fournit une fonction prête à l’emploi binary_search() afin que nous n’ayons pas à implémenter la fonction nous-mêmes. C’est une méthode très simple à utiliser et mise en œuvre efficacement et non sujette aux erreurs.
Vue d’ensemble de C++ STL binary_search()
Syntaxe
DEFAULT
: template <class ForwardIterator, class T>
bool
binary_search(ForwardIterator first, ForwardIterator last, const T& val);
CUSTOM COMPARISON FUNCTION
: template <class ForwardIterator, class T, class Compare>
bool
binary_search(ForwardIterator first, ForwardIterator last, const T& val,
Compare comp);
Ici, T peut être l’un des suivants: int, float, short, long, byte, char, double, et même un Object défini par l’utilisateur comme bien.
Il vérifie si un élément à l’intérieur de [premier, dernier) correspond à l’élément cible X en utilisant l’algorithme de Recherche dichotomique. Par défaut, il utilise l’opérateur less-than pour comparer les éléments, mais nous pouvons également fournir notre propre comp personnalisé comme décrit dans le deuxième modèle donné ci-dessus.
Paramètres
first |
Un itérateur avant pointant vers le premier élément de la plage de tableau donnée. |
last |
Un itérateur vers l’avant pointant vers le dernier élément de la plage de tableau donnée. |
comp |
Une fonction de prédicat binaire définie par l’utilisateur qui accepte deux itérateurs avant comme arguments et renvoie true si les deux arguments sont présents dans le bon ordre. Il ne modifie aucun argument et suit l’ordre strict strict pour ordonner les éléments. |
val |
L’élément cible que nous recherchons dans la plage de tableau donnée. |
Revenir
S’il trouve l’élément cible, il renvoie true; sinon, il retourne false.
Programme C++ pour la Recherche dichotomique
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4, 5, 6};
if (binary_search(v.begin(), v.end(), 5)) {
cout << "Element found" << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
