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 en C# 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 :
 

static void Main(string[ ] args)     {          InitTable ( );          System.Console.WriteLine("Tableau initial :");          AfficherTable ( );          TriInsert ( );          System.Console.WriteLine("Tableau trié :");          AfficherTable ( );           int x = Int32.Parse(System.Console.ReadLine( )), rang;          rang = RechDichoIter( table, x );           if (rang >0)              System.Console.WriteLine("Elément "+x+" trouvé en : "+rang);          else  System.Console.WriteLine("Elément "+x+" non trouvé !");          System.Console.Read();      }

 

Proposition de squelette de classe C# à implanter :
 

class  ApplicationRechDicho   {          static void AfficherTable ( )           {            // Affichage du tableau              ............           }          static void InitTable  ( )           {             ............           }          static void TriInsert ( )           {                // sous-programme de Tri par insertion                 ............           }           static int RechDichoIter( int[] t, int Elt )           {                // Rechreche par dichotomie               ............          }          static void Main(string[ ] args)           {               ............            }    }

Remonter