Discussion :

[parl2871]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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.

[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+.

[druzy]

Il faudrait que tu postes maintenant le code qui correspond à cette erreur

[hwoarang]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

deuxiemetier = (premiertier * 2);

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[parl2871]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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");
		}

[hwoarang]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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");
      }

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[dinobogan]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[hwoarang]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.