Complexité Algorithmique: Les algorithmes de recherche

Ce document présente les principaux algorithmes de recherche en informatique, destinés aux étudiants en informatique ou en sciences numériques. Il couvre la recherche simple, la recherche dichotomique et la recherche par hashage, en détaillant leurs principes, leurs implémentations et les problématiques associées.

Recherche simple

L'algorithme de recherche simple consiste à parcourir un tableau d'éléments pour vérifier la présence d'une valeur donnée. Il s'agit d'une recherche linéaire, où chaque élément est comparé à la valeur recherchée jusqu'à ce qu'une correspondance soit trouvée ou que le tableau soit entièrement parcouru.

public boolean rechercheSimple(int v, int[] T) {
    boolean trouve = false;
    int i = 0;
    while ((trouve == false) && (i < T.length)) {
        if (T[i] == v) {
            trouve = true;
        } else {
            i = i + 1;
        }
    }
    return trouve;
}

Exemple : Pour un tableau T = [3, 7, 1, 9] et une valeur v = 7, l'algorithme compare successivement 3 puis 7. À la deuxième comparaison, il trouve la valeur et retourne true.

Recherche par dichotomie

La recherche dichotomique, ou recherche binaire, s'applique à un tableau trié. Elle consiste à comparer la valeur recherchée à la valeur médiane du tableau, puis à réduire la recherche à la moitié pertinente du tableau selon le résultat de la comparaison.

• Si la valeur médiane est égale à la valeur recherchée, la recherche s'arrête et retourne vrai.
• Si la valeur recherchée est inférieure à la valeur médiane, la recherche continue dans la moitié inférieure.
• Si la valeur recherchée est supérieure, la recherche continue dans la moitié supérieure.
• Si le tableau est réduit à zéro élément, la recherche retourne faux.

public boolean rechercheDichotomique(int v, int[] T) {
    boolean stop = false;
    boolean res = false;
    int indd = 0;
    int indf = T.length - 1;
    int indm;

    while (stop == false) {
        if (indd > indf) {
            stop = true;
        } else {
            indm = (indd + indf) / 2;
            if (T[indm] == v) {
                stop = true;
                res = true;
            } else {
                if (v < T[indm]) {
                    indf = indm - 1;
                } else {
                    indd = indm + 1;
                }
            }
        }
    }
    return res;
}

Exemple : Pour un tableau trié T = [1, 4, 7, 9, 12] et une valeur v = 7 :

• Calcul de l'indice médian : (0 + 4) / 2 = 2 → T[2] = 7
• Valeur trouvée, la fonction retourne true immédiatement.

Recherche par hashage

La recherche par hashage repose sur le calcul d'un indice dans une table de hachage à partir d'une fonction de hashage appliquée à la valeur recherchée. Cette méthode permet un accès direct aux données, ce qui peut réduire considérablement le temps de recherche.

Principes de hashage

• Les données sont stockées dans une table à un indice calculé en fonction de leur valeur.
• Les indices sont déterminés par un code de hachage, obtenu via une fonction de hashage.
• Conditions à respecter :
• Si deux données sont identiques, leur code de hachage doit être identique.
• Les codes de hachage doivent être différents pour des données différentes.

Exemple de fonction de hashage pour des entiers

La fonction suivante calcule un indice dans une table de taille 10 :

h(x) = (3.x + 14) mod 10

Supposons un tableau contenant les valeurs 0, 4, 7, 42 :

• h(0) = (3*0 + 14) mod 10 = 14 mod 10 = 4
• h(4) = (3*4 + 14) mod 10 = (12 + 14) mod 10 = 26 mod 10 = 6
• h(7) = (3*7 + 14) mod 10 = (21 + 14) mod 10 = 35 mod 10 = 5
• h(42) = (3*42 + 14) mod 10 = (126 + 14) mod 10 = 140 mod 10 = 0

Gestion des collisions

Une collision se produit lorsque deux valeurs différentes ont le même indice de hashage. Par exemple, si le nombre 22 est inséré :

• h(22) = (3*22 + 14) mod 10 = (66 + 14) mod 10 = 80 mod 10 = 0
• Or, 42 est déjà à l'indice 0, il y a donc collision.

Pour gérer les collisions, plusieurs méthodes existent :

• Sondage linéaire : chercher la première case libre en parcourant la table à partir de l'indice calculé.
• Double hachage : utiliser une deuxième fonction de hachage pour calculer un pas de saut, la formule est :

Hash = (h(x) + i * h2(x)) mod m

où i est l'itération d'insertion commençant à 0.

• Chaînage linéaire : au lieu d'avoir un seul élément par case, chaque case contient une liste chaînée des éléments ayant le même code de hachage.

Sondage linéaire

Cette méthode consiste à parcourir la table à partir de l'indice de hashage jusqu'à trouver une case libre. Elle présente l'inconvénient que la suppression d'éléments est impossible car cela pourrait casser la chaîne de recherche.

Double hachage

Le double hachage réduit les collisions en utilisant une deuxième fonction de hachage pour déterminer le pas de saut dans la table. Cependant, plus la table est remplie, plus la recherche d'une case libre peut devenir longue.

Chaînage linéaire

Cette méthode consiste à stocker plusieurs éléments dans une même case sous forme de liste chaînée. L'algorithme de recherche parcourt cette liste pour trouver l'élément recherché. L'inconvénient majeur est l'utilisation accrue de mémoire pour stocker les listes.

Glossaire des termes clés

• Algorithme de recherche simple : Parcours linéaire d'un tableau pour trouver une valeur.
• Recherche dichotomique : Recherche dans un tableau trié en divisant successivement l'espace de recherche par deux.
• Fonction de hashage : Fonction qui associe une donnée à un indice dans une table de hachage.
• Code de hachage : Résultat de la fonction de hashage, utilisé comme indice dans la table.
• Collision : Situation où deux données différentes ont le même code de hachage.
• Sondage linéaire : Méthode de résolution des collisions consistant à chercher la première case libre en parcourant la table.
• Double hachage : Méthode de résolution des collisions utilisant une deuxième fonction de hashage pour déterminer le pas de saut.
• Chaînage linéaire : Méthode de résolution des collisions où chaque case de la table contient une liste chaînée d'éléments.

Points clés à retenir

• La recherche simple est intuitive mais inefficace pour les grands tableaux.
• La recherche dichotomique est rapide mais nécessite un tableau trié.
• La recherche par hashage offre un accès quasi direct mais doit gérer les collisions.
• Les collisions sont inévitables et doivent être gérées par sondage linéaire, double hachage ou chaînage.
• Chaque méthode de gestion des collisions a ses avantages et inconvénients en termes de complexité et d'utilisation mémoire.