Ne suppose rien, teste-le!

Souhaitant optimiser quelque peu une fonction de recherche d'élément dans un tableau un peu lente, je me suis penché sur une première optimisation assez basique, la recherche par dichotomie.
Son avantage est qu'elle réduit le nombre d'accès aux cases du tableau, et que son temps d'exécution n'évolue pas proportionnellement au nombre d'éléments. La seule contrainte est que le tableau doit être trié.

La précédente fonction de recherche, un simple WHILE qui parcours le tableau jusqu'à trouver l'élément recherché, prend en moyenne 337ms pour rechercher tous les éléments d'un tableau de 10000 entiers.

J'écris quelques tests

Tab[1]:=5;
Tab[2]:=7;
Tab[3]:=9;
CheckEquals(1, CherchePivot(Tab, 5, 1, 3));
CheckEquals(2, CherchePivot(Tab, 7, 1, 3));
CheckEquals(3, CherchePivot(Tab, 9, 1, 3));
CheckEquals(0, CherchePivot(Tab, 2, 1, 3), '2');
CheckEquals(0, CherchePivot(Tab, 10, 1, 3), '10');

et une première fonction qui répond aux tests.

function CherchePivot(Tableau : TabEtude; Valeur, Debut, Fin : Integer) : Integer;
var
Pivot : Integer;
begin
Result:=0;
Pivot:=(Fin-Debut) div 2 + Debut;
if Valeur=Tableau[Pivot] then Result:=Pivot
else begin
if Valeur>Tableau[Pivot] then Debut:=Pivot+1 else Fin:=Pivot-1;
if Debut<=Fin then Result:=CherchePivot(Tableau, Valeur, Debut, Fin);
end;
end;

Soucis, cette fonction prend 1300ms pour effectuer le test. Pardon? Dans quel univers suis-je? En fait, qu'ai-je besoin d'un appel récursif? Je travaille bien sur une sorte d'arbre, mais je n'explore qu'un seul chemin, donc seconde proposition.

function CherchePivot(Tableau : TabEtude; Valeur, Debut, Fin : Integer) : Integer;
var
Pivot : Integer;
begin
Result:=0;
repeat
Pivot:=(Fin-Debut) div 2 + Debut;
if Valeur=Tableau[Pivot]
then Result:=Pivot
else if Valeur>Tableau[Pivot] then Debut:=Pivot+1 else Fin:=Pivot-1;
until (Result<>0) or (Debut>Fin);
end;

Ouf, plus correct sont les 190ms obtenus.

Deux leçons
- parfois en voulant rendre un algo plus rapide on se trompe
- même sans faire cette monumentale erreur, le gain n'est pas miraculeux

ce qui mène à une seule morale : testez, ne supposez jamais. Je vais continuer l'étude tranquillement et vous tenir au courant.