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