La recherche dichotomique



next up previous contents index
Next: Insertion dans une Up: Recherche en table Previous: La recherche séquentielle

La recherche dichotomique

  Une autre technique de recherche en table est la recherche dichotomique. Supposons que la table des noms soit triée en ordre alphabétique (comme l'annuaire des PTT). Au lieu de rechercher séquentiellement, on compare la clé à chercher au nom qui se trouve au milieu de la table des noms. Si c'est le même, on retourne le numéro de téléphone du milieu, sinon on recommence sur la première moitié (ou la deuxième) si le nom recherché est plus petit (ou plus grand) que le nom rangé au milieu de la table. Ainsi

 

procedure Initialisation;
    begin
    nom[1] := 'anne'; tel[1] := 2702;
    nom[2] := 'laure'; tel[2] := 2701;
    nom[3] := 'paul'; tel[3] := 2811;
    nom[4] := 'pierre'; tel[4] := 2805;
    nom[5] := 'roger'; tel[5] := 4501;
    nom[6] := 'yves'; tel[6] := 2806;
    end;

function RechercheDichotomique (x: Chaine): integer;
var i, g, d: integer;
begin
    g := 1; d := N;
    repeat
        i := (g + d) div 2;
        if x < nom[i] then
            d := i-1 else 
            g := i+1;
    until (x = nom[i]) or (g > d);
    if x = nom[i] then
        RechercheDichotomique := tel[i]
    else
        RechercheDichotomique := -1;
end;

Le nombre de comparaisons pour une table de taille est tel que et . Donc . (Dorénavant, sera simplement écrit .) Si la table a 10000 éléments, on aura . C'est donc un gain sensible par rapport aux 5000 opérations nécessaires pour la recherche linéaire. Bien sûr, la recherche linéaire est plus simple à programmer, et sera donc utilisée pour les petites tables. Pour des tables plus importantes, la recherche dichotomique est plus intéressante.

On peut montrer qu'un temps sub-logarithmique est possible si on connaît la distribution des objets. Par exemple, dans l'annuaire du téléphone, ou dans un dictionnaire, on sait a priori qu'un nom commençant par la lettre V se trouvera plutôt vers la fin. En supposant la distribution uniforme, on peut faire une règle de trois pour trouver l'indice de l'élément de référence pour la comparaison, au lieu de choisir le milieu, et on suit le reste de l'algorithme de la recherche dichotomique. Cette méthode est la recherche par interpolation.   Alors le temps de recherche est en , c'est-à-dire 4 opérations pour une table de 10000 éléments, et 5 opérations jusqu'à entrées dans la table!