Dichotomie / récursivité

Version imprimable

30/10/2013, 13h12
thiecret

Dichotomie / récursivité

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

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

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

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:

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