Recherche dichotomique

Question posée à l'examen de juin 1998

Etant donné les déclarations suivantes:

const ListMax = ...;
type
  Status = (Ok, PlusDePlace, DejaPresent);
  Tableau = record
            List: array[1..ListMax] of Integer;{Tableau trié}
            NbEltList: Integer; {Nombre d'éléments contenus dans List}
            end;

procedure Trouver(Elt: integer; DansTableau: Tableau;
				var Indice: integer; var EltTrouve: boolean);
{Procédure permettant de déterminer si l'élément se trouve dans
 le tableau trié en utilisant la recherche dichotomique.}

procedure Inserer(Elt: integer; var DansTableau: Tableau;
				var EtatInsertion: Status);
{Procédure permettant d'insérer un élément dans le tableau trié.
 La procédure retourne l'état de l'insertion.}

procedure Supprimer(Elt: integer; var DansTableau: Tableau;
				var SupprimerOK: boolean);
{Procédure permettant de supprimer un élément dans le tableau trié
 List. La suppression est possible si l'élément existe dans le
 tableau}

Ecrire le corps des procédures déclarées ci-dessus:

1. Procedure Trouver en tenant compte que la recherche est dichotomique et que la variable Indice fournit la position de l'élément trouvé dans le tableau, ou à la limite, le dernier indice où pourra se faire une éventuelle insertion ultérieure de l'élément.
2. Procedure Inserer en considérant tous les cas possibles de l'insertion. La variable
   EtatInsertion retourne Ok si l'insertion s'est parfaitement effectuée sinon PlusDePlace ou DejaPresent, selon la cause respective de l'échec de l'insertion.
3. Procedure Supprimer en considérant que l'on ne laisse pas un trou dans le tableau quand on élimine un élément.

Site Hosting: Bronco