Recherche dichotomique et méthodes associées en C++ - Bibliothèque STL
Les méthodes de recherche dichotomique supposent qu'une séquence cible est déjà triée. Ces méthodes présentent des caractéristiques de complexité souhaitables par rapport à la recherche générique sur une séquence non spécifiée.
Fonction binary_search
L'algorithme binary_search permet de trouver un élément particulier dans une séquence triée.
La fonction renvoie vrai si la séquence contient la valeur val. Plus précisément, il renvoie vrai si la séquence cible contient un élément x tel que ni x < val ni val < x.
Si fct_comp est fourni, il renvoie vrai si la séquence cible contient un élément x tel que ni fct_comp(x, val) ni fct_comp(val, x).
La séquence cible doit être triée selon operator< ou fct_comp si elle est fournie.
Syntaxe
bool binary_search(fwd_debut, fwd_fin, val, [fct_comp]);
Arguments
- Une paire de ForwardIterators, fwd_debut et fwd_fin, représentant la séquence cible.
- Une valeur à rechercher (val)
- Un opérateur de comparaison facultatif, fct_comp.
Exemple 1
#include<iostream> #include<algorithm> #include<vector> using namespace std; bool fct_comp (int i,int j) { return (i<j); } int main () { int vals[] = {1,2,3,4,5,4,3,2,1}; vector<int> v(vals,vals+9); // Trier le vecteur sort (v.begin(), v.end()); if (binary_search (v.begin(), v.end(), 3)) cout << "La valeur 3 est trouvée.\n"; else cout << "La valeur 3 est introuvable.\n"; // Utiliser fct_as comme opérateur de comparaison: sort (v.begin(), v.end(), fct_comp); if (binary_search (v.begin(), v.end(), 8, fct_comp)) cout << "La valeur 8 est trouvée.\n"; else cout << "La valeur 8 est introuvable.\n"; return 0; }
Résultat
La valeur 3 est trouvée. La valeur 8 est introuvable.
Fonction lower_bound
L'algorithme lower_bound trouve une partition dans une séquence triée. L'algorithme renvoie un itérateur correspondant à l'élément résultat, qui partitionne la séquence de sorte que les éléments avant résultat sont inférieurs à la valeur val, tandis que résultat et tous les éléments après lui ne sont pas inférieurs à la valeur val.
Syntaxe
ForwardIterator lower_bound(fwd_debut, fwd_fin, val, [fct_comp]);
Arguments
- Une paire de ForwardIterators, fwd_debut et fwd_fin, représentant la séquence cible.
- Une valeur pour partitionner la séquence cible avec (val)
- Un opérateur de comparaison facultatif, fct_comp.
Exemple 2
#include<iostream> #include<algorithm> #include<vector> using namespace std; void afficher(int a) { cout << a << " "; } int main () { int vals[] = {1,2,3,2,3,4,5,13,8,9,6}; vector<int> v(vals,vals+10); // Trier le vecteur sort (v.begin(), v.end()); for_each(v.begin(),v.end(), afficher); cout<<'\n'; vector<int>::iterator low; low=lower_bound (v.begin(), v.end(), 4); cout << "La partition est en position " << (low- v.begin()) << '\n'; return 0; }
Résultat
1 2 2 3 3 4 5 8 9 13 La partition est en position 5
Fonction upper_bound
L'algorithme upper_bound trouve une partition dans une séquence triée. L'algorithme renvoie un itérateur correspondant à l'élément résultat, qui est le premier élément de la séquence cible supérieur à la valeur val.
Syntaxe
ForwardIterator upper_bound(fwd_debut, fwd_fin, valeur, [fct_comp]);
Arguments
- Une paire de ForwardIterators, fwd_debut et fwd_fin, représentant la séquence cible.
- Une valeur pour partitionner la séquence cible avec (val)
- Un opérateur de comparaison facultatif, fct_comp.
Exemple 3
#include<iostream> #include<algorithm> #include<vector> using namespace std; void afficher(int a) { cout << a << " "; } int main () { int vals[] = {1,2,3,2,3,4,5,13,8,9,6}; vector<int> v(vals,vals+10); // Trier le vecteur sort (v.begin(), v.end()); for_each(v.begin(),v.end(), afficher); cout<<'\n'; vector<int>::iterator up; up=upper_bound (v.begin(), v.end(), 4); cout << "Le premier élément supérieur à 4 se trouve dans la position " << (up- v.begin()) << '\n'; return 0; }
Résultat
1 2 2 3 3 4 5 8 9 13 Le premier élément supérieur à 4 se trouve dans la position 6
Fonction equal_range
L'algorithme equal_range trouve une plage de certains éléments dans une séquence triée. L'algorithme renvoie un std::pair d'itérateurs correspondant à la plage semi-ouverte égale à la valeur val.
Syntaxe
ForwardIteratorPair equal_range(fwd_debut, fwd_fin, valeur, [fct_comp]);
Arguments
- Une paire de ForwardIterators, fwd_debut et fwd_fin, représentant la séquence cible.
- Une valeur à rechercher (val).
- Un opérateur de comparaison facultatif, fct_comp.
Exemple 4
#include<iostream> #include<algorithm> #include<vector> using namespace std; void afficher(int a) { cout << a << " "; } int main () { int vals[] = {1,2,3,2,3,4,5,13,4,9,4}; vector<int> v(vals,vals+11); pair<vector<int>::iterator,vector<int>::iterator> limites; // Trier le vecteur sort (v.begin(), v.end()); for_each(v.begin(),v.end(), afficher); cout<<'\n'; limites=equal_range (v.begin(), v.end(), 4); cout << "Les valeurs répétées de 4 se trouvent dans l'intervalle [" << (limites.first- v.begin()) << ", "; cout << (limites.second- v.begin())<< "["; return 0; }
Résultat
1 2 2 3 3 4 4 4 5 9 13 Les valeurs répétées de 4 se trouvent dans l'intervalle [5, 8[