Algorithmique impérative/Recherche

Problèmatique

Supposons que nous avons déclaré un tableau tab d'entiers comme suit :

Variables
  tab : tableau MIN à MAX de entiers

Supposons que ce tableau est rempli d'entiers inconnus mais triés dans l'ordre croissant.

Proposez un algorithme qui, étant donné un entier indiqué par l'utilisateur, trouve son indice dans le tableau. On supposera que l'entier indiqué par l'utilisateur est effectivement dans le tableau.

Aide

Vous remarquerez que ce problème s'apparente au problème de recherche d'un mot dans le dictionnaire. Pensez donc à la méthode que vous employez dans cette situation...

Solutions

Solutions moyennes

Voici une solution, qui n'est pas celle attendue. L'algorithme parcourt le tableau du début à la fin et compare l'élément à l'entier indiqué par l'utilisateur. Il s'arrête lorsqu'il est trouvé. Remarquez que la faiblesse de cette algorithme provient du fait qu'il fonctionne même quand le tableau n'est pas trié, il n'exploite donc pas cet avantage trop important pour être négligé.

Algorithme recherche
Variables
  q : entier (* l'entier recherché *)
  i : entier (* ce sera l'indice de parcours *)
Début
  Afficher("Donner l'entier à trouver")
  Lire(q)
  i ← MIN
  tantque tab[i] != q
    i ← i+1
  ftq
  Afficher("L'indice où se trouve ", q ," est ", i)
Fin

L'algorithme suivant fonctionne mais à le défaut de continuer à parcourir le tableau même quand l'élément a été trouvé.

Algorithme recherche_mauvais
Variables
  q : entier (* l'entier recherché *)
  i : entier (* ce sera l'indice de parcours pour la boucle *)
  résultat : entier (* l'indice résultat sera stocké ici *)
Début
  Afficher("Donner l'entier à trouver")
  Lire(q)
  i ← MIN
  pour i de MIN à MAX (* on parcourt tout le tableau *)
    si tab[i] = q alors résultat ← i (* si on a trouvé on mémorise l'indice *)
  ftq
  Afficher("L'indice où se trouve ", q ," est ", résultat)
Fin

Solution attendue

Voici enfin la solution attendue. Vous étiez peut-être arrivé à cette déduction seul ou en consultant l'aide mais vous avez compris que ce problème s'apparente à celui de la recherche dans un dictionnaire. En effet, on cherche un mot dans un ensemble de mots inconnus mais triés.

Si vous avez déjà cherché un mot dans le dictionnaire, vous avez certainement remarqué que lire le premier, regarder si c'est celui qu'on cherche, puis passer au suivant, et ainsi de suite n'est pas la solution la plus efficace...

La solution est donc l'algorithme de recherche dichotomique (du grec « dichotomie » : « couper en deux »). On ouvre le dictionnaire au milieu et un prend un mot au hasard, si le mot qu'on cherche est avant, recommence avec la première moitié du dictionnaire, s'il est après, avec la deuxième moitié. Dans la bonne moitié on prend un mot au milieu, etc...

Algorithme recherche_dichotomique
Variables
  q : entier         (* l'entier recherché *)
  i : entier         (* ce sera l'indice de parcours pour la boucle *)
  deb, fin : entiers (* deux entiers pour désigner le début et la fin de la zone dans laquelle on recherche *)
Début
  Afficher("Donner l'entier à trouver")
  Lire(q)
  (* on commence en recherchant dans tout le tableau *)
  deb ← MIN
  fin ← MAX
  répéter
    i = arrondir((fin+deb)/2) (* on prend i entre deb et fin *)
    si tab[i] > q
      alors fin ← i (* on est tombé trop haut : on ramène la borne supérieure *)
      sinon si tab[i] < q
              alors deb ← i (* on est tombé trop bas : on ramène la borne inférieure *)
  jusqu'à tab[i]=q
  Afficher("L'indice où se trouve ", q ," est ", i)
Fin

Traduction en Pascal

Voilà sa traduction en Pascal, le tableau étant rempli à la main :

program recherche_dichotomique;
Const
  MIN = 0;
  MAX = 10;
Var
  tab : array [MIN..MAX] of integer;
  q : integer;         (* l'entier recherché *)
  i : integer;         (* ce sera l'indice de parcours pour la boucle *)
  deb, fin : integer;  (* deux entiers pour désigner le début et la fin de la zone dans laquelle on recherche *)
Begin
  tab[0] := 1;
  tab[1] := 4;
  tab[2] := 9;
  tab[3] := 10;
  tab[4] := 24;
  tab[5] := 24;
  tab[6] := 74;
  tab[7] := 75;
  tab[8] := 76;
  tab[9] := 90;
  tab[10] := 99;
  Writeln('Donner l''entier à trouver : ');
  Readln(q);
  (* on commence en recherchant dans tout le tableau *)
  deb := MIN;
  fin := MAX;
  repeat
    i := round((fin+deb)/2); (* on prend i entre deb et fin *)
    if tab[i] > q
      then fin := i (* on est tombé trop haut : on ramène la borne supérieure *)
      else if tab[i] < q
              then deb := i; (* on est tombé trop bas : on ramène la borne inférieure *)
  until tab[i]=q;
  Writeln('L''indice où se trouve ', q ,' est ', i);
End.