Recherche dichotomique en Pascal

principe de la méthode :

 pour chercher une valeur « élem » dans un tableau t1 nous allons utiliser la  fonction      

 recherche_dichotomique qui renvoi  TRUE si « elem » existe dans le tableau t1 et FALSE sinon.

La recherche dichotomique doit être appliquée sur un tableau dont les éléments sont triés.

Le principe de la recherche dichotomique est le suivant :

 On regarde l’élément au milieu du tableau.

- S’il est égal à la valeur cherchée « élem », l’élément cherché est existant.

- S’il est inférieur a la valeur recherchée « élem »  ,il ne reste à traiter que la moitié droite du tableau.

- S’il est supérieur à la valeur recherchée « élem », il ne reste à traiter que la moitié gauche du tableau.

On continue ainsi la recherche en diminuant à chaque fois de moitié le nombre d’éléments du tableau restant à traiter.

Traduction en pascal du programme principale :

program recherche_sequentielle;

uses wincrt;

type

 tab = ARRAY[1..100] of integer;

var

   tail ,x :integer;

   trouve: boolean;

   t1: tab;

PROCEDURE permuter(var t :tab ; k,l:integer);

var

aux : integer;

begin

  aux  := t[k];

  t[k] := t[l];

  t[l] := aux;

end;

PROCEDURE tri_bulle(var t : tab; n:integer ); { pour tirer le atbelau on à utiliser le trie à bulle }

var

i,j: integer;

begin

for i:=n downto 1 do

for j:=1 to n-1 do

 if t[j]>t[j+1] then permuter(t,j,j+1);

end;

FUNCTION recherche_dichotomique(t: tab;n,elem:integer): boolean;

var

existe: boolean;

gauche,droite: integer;

milieu: integer;

begin

gauche := 1;

droite := n;

repeat

        milieu := (gauche+droite) DIV 2;

        if (t[milieu] = elem ) then existe := true

                                  

else

   if(t[milieu]> elem) then droite := milieu-1

 else

   gauche := milieu+1;                         

until ( (existe = true) or (gauche > droite) );

recherche_dichotomique:= existe;

end; { fin focntion recherhce dichotomique }

PROCEDURE saisie(var t: tab; n :integer);

var

i: integer;

begin

  for i:=1 to n do

    begin

      writeln('donner un entier');

      readln(t[i]);

    end;

end;

 PROCEDURE saisie_tail(VAR n:integer);

 begin

 repeat

   writeln('donner la taille du tableau');

   readln(n);

 until n in [10..20];

 end;

 BEGIN

 saisie_tail(tail);

 saisie(t1,tail);

 writeln('donner lelement a chercher ');

 readln(x);

 tri_bulle(t1,tail);

 trouve := recherche_dichotomique(t1,tail,x);

  if( trouve = true) then writeln('lement existe dans le tableau ')

    else

      writeln('l''element nexiste pas dans le tableau');

 END.