Source : Adapté depuis QCM prologin 2002

On vous donne une suite d'entiers triée dans l'ordre croissant. Ecrire un programme qui détermine le nombre le plus proche, dans cette suite, de chacune des valeurs d'une deuxième liste. S'il y a plusieurs possibilités, votre programme doit choisir la plus petite valeur.

En entrée vous lisez :

• Le nombre N d'entiers de la suite.
• Les entiers de la suite, séparés par des espaces.
• Le nombre R d'entiers à rechercher.
• Les entiers à rechercher, séparés par des espaces.

Exemple

• Entrée :
  

  10
  0 1 2 3 4 5 6 7 8 9
  2
  7 14

• Sortie : 
  7 9

Correction :

Par : Ahmed Fessi

En Pascal :

program ClosestNumber;
var
Suite:array[1..100000] of integer;
Rech:array[1..1000] of integer;
Long_Suite,i:integer;
nbr_rech:integer;

Function DichotomicSearch(element,a,b:integer):integer;
var
mid:integer;
begin
Mid:=(a+b) div 2;
if (element<=Suite[Mid+1]) and (element>=Suite[Mid]) then
begin
	if (Suite[Mid+1]-element)<(element-Suite[Mid]) 
	then DichotomicSearch:=Suite[Mid+1] 
        else DichotomicSearch:=Suite[Mid];
end
else
if (element<Suite[Mid]) then DichotomicSearch:=DichotomicSearch(element,a,Mid)
else DichotomicSearch:=DichotomicSearch(element,Mid+1,b);
end;



begin
readln(long_suite);
For i:=1 to long_Suite-1 do
	read(Suite[i]);
readln(Suite[Long_Suite]);
readln(nbr_rech);
For i:=1 to nbr_rech do
	read(Rech[i]);

For i:=1 to nbr_rech do
begin
        if rech[i]<=Suite[1] then write(Suite[1])
        else if rech[i]>=Suite[Long_Suite] then write(Suite[long_Suite])
        else
	write(DichotomicSearch(rech[i],1,Long_Suite));
        if i<>nbr_rech then write(' ');
end;
writeln;
end.