lundi 26 février 2001

Recherche


LES RECHERCHES

Nous utilisons différents types de recherche pour trouver des données spécifiques. Nous verrons qu'il y a divers types de recherche qui peuvent être faites.

Type de recherche

La recherche séquentielle

La recherche séquentielle consiste à vérifier du début  du tableau, liste... jusqu'à ce qu'on trouve ce qu'on désire ou parcoure totalement le tableau liste... C'est évidemment pas la recherche la plus efficace. Ce type de recherche est doit être utilisé si le tableau n'est pas trié.
//on définit les variables utilisées
Const
  Max=15;
  type
    tabType = array [1..Max] of integer;
function SequentialSearch(tab:tabType; item:integer):integer;
var
  i : integer;
  found : boolean;
begin
  SequentialSearch := 0;
  i := low(tab);
  found := false;
  while( i <= high(tab)) and (not found) do
  begin
    if tab[i] = item then
    begin
      SequentialSearch := i;
      found := true;
    end;
    inc(i);
  end;
end;

La recherche binaire

La recherche séquentielle consiste à comparer la valeur recherché par le milieu du vecteur.Si cet élément est plus grand que l'élément recherché, ce dernier est à gauche sinon à droite. On répète l'opération sur les sous-vecteurs. Le tableau doit évidemment être trié pour tirer parti de ce type de recherche

function BinarySearch(tab:tabType; item:integer):integer;
var
  Milieu:integer;
  Found:boolean;
  bas:integer;
  haut:integer;
begin
  bas := low(tab);
  haut := high(tab);
  Found := False;
  BinarySearch := 1;
  while(bas <= haut) and (not Found) do
  begin
    Milieu := (bas + haut) div 2;
    if tab[Milieu] = item then
    begin
      Found := True;
      BinarySearch := Milieu;
    end
    else
      if tab[Milieu] < item then
        bas := Milieu + 1
      else
        haut := Milieu - 1;
  end;
end;