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.

Complexité

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

1. Algorithme binary_search

Description

L'algorithme binary_search permet de trouver un élément particulier dans une séquence triée.

La fonction renvoie true si la séquence contient la valeur val. Plus précisément, elle 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, elle renvoie vrai si la séquence cible contient un élément x tel que ni fct_comp(x, val) ni fct_comp(val, x).

Condition importante

La séquence cible doit être triée selon operator< ou fct_comp si elle est fournie.

Syntaxe

binary_search C++

bool binary_search(fwd_debut, fwd_fin, val, [fct_comp]);

Arguments

fwd_debut, fwd_fin : une paire de ForwardIterators représentant la séquence cible
val : la valeur à rechercher
fct_comp (optionnel) : un opérateur de comparaison

Exemple 1 : Recherche dichotomique simple

#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 (obligatoire pour binary_search)
    sort(v.begin(), v.end());

    // Recherche de la valeur 3
    if (binary_search(v.begin(), v.end(), 3))
        cout << "La valeur 3 est trouvée.\n";
    else
        cout << "La valeur 3 est introuvable.\n";

    // Tri avec fonction de comparaison personnalisée
    sort(v.begin(), v.end(), fct_comp);

    // Recherche de la valeur 8 avec la même fonction de comparaison
    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.

Explication :

Le vecteur est d'abord trié avec sort() (indispensable).
binary_search retourne true car 3 est présent.
8 n'est pas présent dans le vecteur, donc false.

2. Algorithme lower_bound

Description

L'algorithme lower_bound trouve une partition dans une séquence triée. Il renvoie un itérateur correspondant au premier élément non inférieur à la valeur val.

Plus précisément, l'algorithme renvoie un itérateur résultat qui partitionne la séquence de sorte que :

Tous les éléments avant résultat sont inférieurs à val
résultat et tous les éléments après lui sont non inférieurs à val (c'est-à-dire >= val)

Syntaxe

lower_bound C++

ForwardIterator lower_bound(fwd_debut, fwd_fin, val, [fct_comp]);

Arguments

fwd_debut, fwd_fin : une paire de ForwardIterators représentant la séquence cible
val : la valeur pour partitionner la séquence
fct_comp (optionnel) : un opérateur de comparaison

Exemple 2 : Utilisation de lower_bound

#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());
    
    // Affichage du vecteur trié
    cout << "Vecteur trié : ";
    for_each(v.begin(), v.end(), afficher);
    cout << '\n';

    // lower_bound pour la valeur 4
    vector<int>::iterator low;
    low = lower_bound(v.begin(), v.end(), 4);

    cout << "La partition est en position " << (low - v.begin()) << '\n';
    cout << "Valeur à cette position : " << *low << '\n';

    return 0;
}

Résultat

Vecteur trié : 1 2 2 3 3 4 5 8 9 13 
La partition est en position 5
Valeur à cette position : 4

Explication :

Le vecteur trié est : 1, 2, 2, 3, 3, 4, 5, 8, 9, 13
lower_bound(v.begin(), v.end(), 4) retourne l'itérateur vers le premier élément >= 4
C'est la position 5 (le premier 4)
Tous les éléments avant la position 5 sont inférieurs à 4

3. Algorithme upper_bound

Description

L'algorithme upper_bound trouve une partition dans une séquence triée. Il renvoie un itérateur correspondant au premier élément strictement supérieur à la valeur val.

Syntaxe

upper_bound C++

ForwardIterator upper_bound(fwd_debut, fwd_fin, val, [fct_comp]);

Exemple 3 : Utilisation de upper_bound

#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());
    
    // Affichage du vecteur trié
    cout << "Vecteur trié : ";
    for_each(v.begin(), v.end(), afficher);
    cout << '\n';

    // upper_bound pour la valeur 4
    vector<int>::iterator up;
    up = upper_bound(v.begin(), v.end(), 4);

    cout << "Le premier élément supérieur à 4 se trouve à la position " << (up - v.begin()) << '\n';
    cout << "Valeur à cette position : " << *up << '\n';

    return 0;
}

Résultat

Vecteur trié : 1 2 2 3 3 4 5 8 9 13 
Le premier élément supérieur à 4 se trouve à la position 6
Valeur à cette position : 5

Explication :

upper_bound(v.begin(), v.end(), 4) retourne l'itérateur vers le premier élément > 4
C'est la position 6 (valeur 5)
Tous les éléments avant la position 6 sont <= 4

4. Algorithme equal_range

Description

L'algorithme equal_range trouve une plage de certains éléments dans une séquence triée. Il renvoie une paire d'itérateurs correspondant à la plage semi-ouverte égale à la valeur val.

La paire retournée est équivalente à :

make_pair(lower_bound(...), upper_bound(...))

Syntaxe

equal_range C++

pair<ForwardIterator,ForwardIterator> equal_range(fwd_debut, fwd_fin, val, [fct_comp]);

Exemple 4 : Trouver tous les éléments égaux à une valeur

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

    // Trier le vecteur
    sort(v.begin(), v.end());
    
    // Affichage du vecteur trié
    cout << "Vecteur trié : ";
    for_each(v.begin(), v.end(), afficher);
    cout << '\n';

    // equal_range pour la valeur 4
    pair<vector<int>::iterator, vector<int>::iterator> limites;
    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()) << ", "
         << (limites.second - v.begin()) << "[\n";

    // Affichage des valeurs dans l'intervalle
    cout << "Valeurs dans cet intervalle : ";
    for (vector<int>::iterator it = limites.first; it != limites.second; ++it) {
        cout << *it << " ";
    }
    cout << '\n';

    return 0;
}

Résultat

Vecteur trié : 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[
Valeurs dans cet intervalle : 4 4 4

Explication :

equal_range retourne deux itérateurs : le premier (lower_bound) et le dernier (upper_bound) des éléments égaux à 4.
L'intervalle [5, 8[ contient trois fois la valeur 4 (positions 5, 6, 7).
La borne supérieure (position 8) pointe vers la valeur 5, premier élément > 4.

Récapitulatif des algorithmes de recherche dichotomique

Algorithme	Retourne	Condition sur la séquence	Utilité
binary_search	`bool`	Triée	Vérifier si une valeur existe
lower_bound	Itérateur	Triée	Premier élément >= val
upper_bound	Itérateur	Triée	Premier élément > val
equal_range	Paire d'itérateurs	Triée	Intervalle des éléments == val

Relation entre les algorithmes

Pour une séquence triée et une valeur val :

lower_bound donne la première position où insérer val sans casser l'ordre
upper_bound donne la dernière position où insérer val sans casser l'ordre
equal_range combine les deux en une seule opération
binary_search teste simplement si val est présent

Exercice pratique

Utilisation des algorithmes dichotomiques

Niveau : Intermédiaire

On considère le vecteur suivant (non trié) :

vector<int> v = {8, 3, 5, 1, 9, 3, 7, 3, 6, 2};

Questions :

Quelle opération faut-il effectuer avant d'utiliser les algorithmes de recherche dichotomique ?
Après avoir trié le vecteur, quelles seront les positions retournées par lower_bound, upper_bound et equal_range pour la valeur 3 ?
Que retournerait binary_search pour la valeur 4 ?
Écrire un code qui affiche toutes les positions où se trouve la valeur 3 en utilisant equal_range.

Solution

Opération préalable :
Il faut trier le vecteur avec sort(v.begin(), v.end()) car tous ces algorithmes exigent une séquence triée.
Après tri :
Le vecteur trié devient : {1, 2, 3, 3, 3, 5, 6, 7, 8, 9}
- lower_bound(3) : premier élément >= 3 → position 2 (valeur 3)
- upper_bound(3) : premier élément > 3 → position 5 (valeur 5)
- equal_range(3) : intervalle [2, 5[ (positions 2, 3, 4)
binary_search(4) :
Retourne false car 4 n'est pas présent dans le vecteur.

Code pour afficher les positions de 3 :

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {8, 3, 5, 1, 9, 3, 7, 3, 6, 2};
    
    // Tri obligatoire
    sort(v.begin(), v.end());
    
    // Recherche de la plage des 3
    auto p = equal_range(v.begin(), v.end(), 3);
    
    cout << "Le vecteur trié : ";
    for (int x : v) cout << x << " ";
    cout << "\nLa valeur 3 se trouve aux positions : ";
    
    for (auto it = p.first; it != p.second; ++it) {
        cout << (it - v.begin()) << " ";
    }
    cout << endl;
    
    return 0;
}

Sortie

Le vecteur trié : 1 2 3 3 3 5 6 7 8 9 
La valeur 3 se trouve aux positions : 2 3 4

Points clés à retenir

Les algorithmes de recherche dichotomique nécessitent que la séquence soit triée au préalable.
Complexité : O(log N) pour les itérateurs à accès aléatoire (vector, deque), O(N) sinon.
binary_search : teste simplement l'existence d'une valeur (retourne bool).
lower_bound : retourne le premier élément non inférieur à val (>= val).
upper_bound : retourne le premier élément strictement supérieur à val (> val).
equal_range : retourne une paire [lower_bound, upper_bound[ représentant tous les éléments égaux à val.
Ces algorithmes sont très efficaces pour les recherches dans de grands ensembles de données triés.
Ils sont souvent utilisés en combinaison avec sort() et les conteneurs associatifs (set, map).

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

Algorithmes de recherche dichotomique

1. Algorithme binary_search

Syntaxe

Arguments

Exemple 1 : Recherche dichotomique simple

2. Algorithme lower_bound

Syntaxe

Arguments

Exemple 2 : Utilisation de lower_bound

3. Algorithme upper_bound

Syntaxe

Exemple 3 : Utilisation de upper_bound

4. Algorithme equal_range

Syntaxe

Exemple 4 : Trouver tous les éléments égaux à une valeur

Récapitulatif des algorithmes de recherche dichotomique

Utilisation des algorithmes dichotomiques

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

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

Algorithmes de recherche dichotomique

1. Algorithme binary_search

Syntaxe

Arguments

Exemple 1 : Recherche dichotomique simple

2. Algorithme lower_bound

Syntaxe

Arguments

Exemple 2 : Utilisation de lower_bound

3. Algorithme upper_bound

Syntaxe

Exemple 3 : Utilisation de upper_bound

4. Algorithme equal_range

Syntaxe

Exemple 4 : Trouver tous les éléments égaux à une valeur

Récapitulatif des algorithmes de recherche dichotomique

Utilisation des algorithmes dichotomiques

Discussion (0)

Laisser un commentaire