Discussion :

[thiecret]

Bonjour,

J'ai ajouté une réponse sur un poste, mais comme ce dernier a été résolu, je ne sais pas si quelqu'un va répondre, donc, je crée un nouveau poste.

Voici le lien du post que j'ai précité : http://www.developpez.net/forums/d70...e/#post7547730

Voila, dans ce poste sur la dichotomie récursive, je me demandais ou il fallait ajouter "return -1;" au cas ou la valeur n'existe pas dans le tableau ?

Je compte sur votre aide.

Merci d'avance,

TC

[thiecret]

RE:
Ca devrait donner quelque chose comme ca, mais ca me fait un stackoverflow :

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
 
 
public class RecursifDichotomique 
{
	public static void main(String[] args) 
	{
		RecursifDichotomique rd = new RecursifDichotomique();
		int[] tableau = {2,4,5,12,14,15,17,23,52,65,76,86,89,91,95,102,103};
 
		System.out.println(rd.recursifDichotomique(0, tableau.length, tableau, 3));
	}
 
	public int recursifDichotomique(int debut, int fin, int[]tableau, int cle)
	{
		//clause de finitude
		if(debut > fin)
		{
			return -1;
		}
		if(tableau[(debut+fin)/2] == cle)
		{
			return (debut+fin)/2;
		}
		if(cle < tableau[(debut+fin)/2])
		{
			return recursifDichotomique(debut, ((debut+fin)/2), tableau, cle);
		}
		else
		{
			return recursifDichotomique(((debut+fin)/2), fin, tableau, cle);
		}
	}
}

[joel.drigo]

Salut,

1er problème : pas de confition de fin sur debut==fin
2ème problème : l'indice mil (le milieu de [0..n[ est traité dans le test
tableau[mil] == cle, donc pas besoin de le retraiter récursivement (en particulier parce qu'on sait déjà qu'il n'est pas égal)

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
public int recursifDichotomique(int debut, int fin, int[] tableau, int cle) {
		  
		if ( debut==fin ) {
			if (tableau[debut] == cle) {
				return debut;
			}
			else {
				return -1;
			}
		}
		else {
			if (debut > fin) {
				return -1;
			}
			int mil = (debut + fin) / 2;
			if (tableau[mil] == cle) {
				return mil;
			}
			else if (cle < tableau[mil]) {
				return recursifDichotomique(debut, mil, tableau,
						cle);
			} else {
				return recursifDichotomique(mil+1, fin, tableau, cle);
			}
		}
	}