Recherche dichotomique

Lorsque l'on recherche un élément dans un tableau, en s'attend à effectuer, en moyenne, des comparaisons avec la moitié des éléments avant de trouver un élément présent dans celui-ci.

Dans l'éventualité où l'élément cherché est absent du tableau, nous devons comparer la valeur cherchée avec la totalité des éléments du tableau avant de pouvoir conclure à l'absence de l'élément cherché.

La recherche dichotomique, sur un tableau trié en fonction du champ sur lequel nous recherchons une valeur, permet de diminuer le nombre moyen de comparaison nécessaires pour conclure à la présence ou non, d'un élément dans le tableau.

Voici une méthode qui effectue la recherche d'un entier aChercher dans un tableau T d'entiers. Si elle la trouve, la méthode retourne l'indice dans le tableau de la valeur cherchée, sinon, elle retourne –1.

int dicho(int[] T, int aChercher){

int  mini, maxi, milieu ;  // les indices

boolean trouve = false ;

 

mini   = 0 ;

maxi   = T.length - 1 ; /* on examine tout le tableau */

 

while ( !trouve && (mini <= maxi) ) {

  milieu = ( mini + maxi ) / 2 ;

 

  if ( aChercher < t[milieu] )

     maxi = milieu - 1 ;

  else

     if ( aChercher > t[milieu] )

         mini = milieu + 1 ;

     else

         trouve = true

}

 

if (trouve)  

   return milieu ;

else  

   return -1 ;

}

Soit le tableau trié suivant :

             -------

     t[0]    |        5      |

             -------

     t[1]    |       20      |

             -------

     t[2]    |       27      |

             -------

     t[3]    |       49      |

             -------

     t[4]    |       79      |

             -------

     t[5]    |       90      |

             -------

     t[6]    |      100      |

             -------

Exemple avec une valeur présente dans le tableau

Supposons que l'on recherche la valeur 90.

Initialement, la valeur du milieu est à l'indice 3, t[3] < 90, donc on sait que si la valeur cherchée est dans le tableau, elle doit être entre les indices 4 et 6.

À la 2ième itération, la valeur du milieu est à l'indice (6+4)/2, t[5] == 90, donc nous avons trouvé.

Exemple avec une valeur absente du tableau

Supposons maintenant que la valeur cherchée est 88 ( qui est absente du tableau ).

Initialement, la valeur du milieu est à l'indice 3, t[3] < 88, donc on sait que si la valeur cherchée est dans le tableau, elle doit être entre les indices 4 et 6.

À la 2ième itération, la valeur du milieu est à l'indice (6+4)/2, t[5] > 88, donc si la valeur cherchée est dans le tableau elle doit être entre les indices 4 et 4.

À la 3ième itération, la valeur du milieu est à l'indice 4, t[4]<88, donc la valeur devrait se trouver entre les indices 4 et 3, comme mini > maxi, on sait que la valeur cherchée n'est pas dans le tableau.

Exercice

Écrivez une classe Pizza qui a un rayon et un vecteur d'ingrédients (String).

Votre classe Pizza doit implémenter l'interface comparable de manière à ce que la relation d'ordre dépende d'abord du rayon, ensuite du nombre d'ingrédients sur la pizza et finalement, pour un rayon et nombre d'ingrédients égaux, des ingrédients eux-mêmes (ordre à votre choix).

Créez un tableau de Pizza. Utilisez la méthode de tri pour les objets comparable du chapitre 6, voir fichier Sorts.java pour trier ce tableau.

Implementez une méthode de recherche dichotomique pour les objets comparable et utilisez celle-ci pour chercher des pizza dans le tableau de Pizza.