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.

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.
                

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
                

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
                

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[