Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité
Introduction et syntaxe de base
Pointeurs et fonctions
Programmation OO
Structures de données
La bibliothèque standard (STL)

Recherche dichotomique et méthodes associées en C++ - Bibliothèque STL

 

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.

Tous les algorithmes ci-dessous fournissent une complexité logarithmique \(O(log N)\)  (N = distance (fwd_debut, fwd_fin)) si un itérateur à accès aléatoire est donné, sinon c'est une complexité linéaire.

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[
                

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.