Algorithme de recherche Trichonomique

Version imprimable

Salut à tous,

Je tente de régler un petit algorithme de recherche dans un tableau et j'ai des problèmes d'exécution. Je suis débutant à ce niveau.

Voila ce que j'ai :
La valeur x est celle que je cherche
78 ici comme exemple

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
        int tableau[] = { 2, 4, 10, 22, 34, 40, 56, 61, 78, 90 };
        int x = 78;
        int debut = 0;
        int fin = 9;
        int premiertier = (debut + fin) / 3;
        int deuxiemetier = (premiertier * 2);
 
        while ((debut < fin) && (x != tableau[premiertier])) {
 
            if (x < tableau[premiertier]) {
 
                fin = premiertier;
            }
            else if (x > tableau[deuxiemetier]) {
 
                debut = deuxiemetier;
            }
            else {
 
                debut = premiertier;
                fin = deuxiemetier;
            }
 
            premiertier = (debut + fin) / 3;
            deuxiemetier = (premiertier * 2);
        }
 
        if (tableau[premiertier] == x) {
 
            System.out.println("La valeur " + x + " se trouve à la position "
                    + premiertier);
        }
        else {
 
            System.out.println("La valeur n'a pas été trouvée");
        }

Voici le message d'erreur que j'obtiens :

Citation:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at dicho3.main(dicho3.java:17)

Quelqu'un saurait-il m'indiquer d'où peut venir le problème ?

Merci d'avance pour votre aide.

30/01/2013, 04h56
andry.aime

Bonjour,

C'est que l'index que tu tentes d'accéder dans le tableau est égal ou supérieur à la taille du tableau. L'index qui est accepté est de 0 à taille-1.

A+.
30/01/2013, 13h31
druzy

Il faudrait que tu postes maintenant le code qui correspond à cette erreur
30/01/2013, 14h08
hwoarang

Tu as un probleme de limite lors du calcul de l'indice de fin de recherche.
Il faut remplacer :

Code:

deuxiemetier = (premiertier * 2);

par

Code:

deuxiemetier = Math.min((premiertier * 2), tableau.length-1);

Parce que actuellement, tu essayes d'acceder à un indice supérieur à la taille du tableau.

C'est bon sauf que cette fois j'ai l'impression d'être dans une boucle infini.
Pas d'erreur mais la machine virtuel tourne... Je dois forçer un break...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int tableau[] = { 2, 4, 10, 22, 34, 40, 56, 61, 78, 90 };
		int x = 78;
		int debut = 0;
		int fin = 9;
		int premiertier = (debut + fin) / 3;
		int deuxiemetier = Math.min((premiertier * 2), tableau.length-1);
 
		while ((debut < fin) && (x != tableau[premiertier])) {
 
			if (x < tableau[premiertier]) {
				fin = premiertier;
			}
 
			else if (x > tableau[deuxiemetier]) {
				debut = deuxiemetier;
			}
 
			else{
				debut = premiertier;
				fin = deuxiemetier;
			}
 
			premiertier = (debut + fin) / 3;
			deuxiemetier = Math.min((premiertier * 2), tableau.length-1);
		}
		if (tableau[premiertier] == x) {
 
			System.out.println("La valeur " + x + " se trouve à la position "
					+ premiertier);
 
		}
 
		else {
			System.out.println("La valeur n'a pas été trouvée");
		}

Je trouve ca plus simple intellectuellement de raisonner avec un index de debut et un pas (ca simplifie le nombre de variables). Par defaut le pas sera egal a taille du tableau / 3. Ainsi, si on est apres l'element au pas suivant, il faut changer le debut. Sinon, il faut diviser par 3 le pas. Ca donnera un truc du genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
      int tableau[] = { 2, 4, 10, 22, 34, 40, 56, 61, 78, 90 };
      int x = 78;
      int debut = 0;
      int pas = (tableau.length / 3);
 
      while (debut < (tableau.length - 1) && (pas > 0))
      {
         int i= Math.min(debut + pas, tableau.length - 1);
         if (x >= tableau[i])
         {
            // On est dans un tiers superieur
            debut = i;
         } 
         else
         {
            // On est dans le meme tier
            pas = pas / 3;
         }
      }
      if (tableau[debut] == x)
      {
 
         System.out.println("La valeur " + x + " se trouve à la position "
               + debut);
      }
      else
      {
         System.out.println("La valeur n'a pas été trouvée");
      }

30/01/2013, 17h26
parl2871

Merci, merci merci
Ça fonctionne bien à ce niveau d'interprétation. wow
Seulement, Je pense ici que nous éliminons qu'un seul tier à chaque tour de boucle while non?
Maintenant, pour ma compréhension java, on peux me traduire en pseudo code la ligne:

Code:

int i= Math.min(debut + pas, tableau.length - 1);

i est égal à...( ??? )
30/01/2013, 17h52
dinobogan

Citation:

Envoyé par parl2871

Merci, merci merci
Ça fonctionne bien à ce niveau d'interprétation. wow
Maintenant, pour ma compréhension java, on peux me traduire en pseudo code la ligne:

Code:

int i= Math.min(debut + pas, tableau.length - 1);

i est égal à...( ??? )

i vaut la plus petite valeur entre les deux valeurs possibles debut + pas et tableau.length - 1
31/01/2013, 09h40
hwoarang

Citation:

Envoyé par parl2871

Seulement, Je pense ici que nous éliminons qu'un seul tier à chaque tour de boucle while non?

Oui, c'est vrai. Pour éliminer plus, il faut partir (comme tu le faisais) sur le tier du milieu et pouvoir éventuellement revenir sur un tier précédent. Ceci dit, le principe est le meme (au niveau de l'evolution du pas - c'etait ca ton erreur). Partir du premier tier donne un code plus simple à comprendre. Une fois compris, tu peux l'adapter comme tu veux.

Quand à

Code:

int i= Math.min(debut + pas, tableau.length - 1);

Le principe, c'est que si tu as éliminé le tier courant, tu passes au tier suivant (c'est à dire debut + pas). Et pour éviter d'etre en dehors du tableau si le nombre d'element n'est pas multiple de 3, on met la borne max à tableau.length - 1.