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 ;
}
-------
t[0]
| 5 |
-------
t[1]
| 20
|
-------
t[2]
| 27 |
-------
t[3]
| 49 |
-------
t[4]
| 79 |
-------
t[5]
| 90 |
-------
t[6] | 100 |
-------
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é.
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.
É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.