Objectif : effectuer une recherche dichotomique dans un tableau linéaire déjà trié.
 

Spécifications de l’algorithme :
 
 

• Soit t un tableau d'entiers de 1..n éléments triés par ordre croissant.

 
• On recherche le rang (la place) de l'élément Elt dans ce tableau. L'algorithme renvoie le rang (la valeur -1 est renvoyée lorsque l'élément Elt n'est pas présent dans le tableau t)

Au lieu de rechercher séquentiellement du premier jusqu'au dernier, on compare l'élément Elt à chercher au contenu du milieu du tableau. Si c'est le même, on retourne le rang du milieu, sinon l'on recommence sur la première moitié (ou la deuxième) si  l'élément recherché est plus petit (ou plus grand) que le contenu du milieu  du tableau.

  Version itérative

bas, milieu, haut, rang : entiers      bas ¬  1;       haut ¬  N;       Rang ¬  -1;       repéter         milieu ¬  (bas + haut) div 2;          si x = t[milieu] alors              Rang ¬  milieu          sinon  si t[milieu] < x alors                       bas ¬  milieu + 1                     sinon                       haut ¬  milieu-1                    fsi         fsi     jusquà ( x = t[milieu] ) ou ( bas > haut )

Implanter une méthode que vous nommerez RechDichoIter qui recevant en entrée un tableau et un élément à chercher, renverra le rang de l'élément selon les spécifications ci-haut. N'oubliez pas de trier le tableau avant d'invoquer la méthode de recherche. Ci-dessous une suggestion de rédaction de la méthode main :

 

Proposition de squelette de classe Java à implanter :
 

Remonter 

---