Discussion :

[noussa17]

salut a tous,
j'ai pas compris comment écrire une fonction récursive qui utilise la méthode DICOTHOMIQUE pour chercher un élément E dans un tableau Tab
svp donnez moi une idée sur cette méthode.
.

[Pouet_forever]

Il faut d'abord bien cerner ce qu'est la recherche dichotomique.
Déjà pour commencer il te faut un tableau trié !
Ensuite, il faut comparer l'élément du milieu à l'élément recherché.
Si c'est plus grand il faut recommencer la recherche en prenant le milieu de l'intervalle le plus grand : ]milieu, fin]
Si c'est plus petit c'est l'inverse : [début, milieu[
Si c'est égal il faut retourner la valeur.

Du coup pour ta fonction il te faudra au moins 3 paramètres :
- L'élément recherché,
- La borne supérieure,
- La borne inférieure.
Et en général le tableau concerné.

Don au final ta fonction devrais avoir 4 paramètres.

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
Fonction dichotomique (tableau, nombre recherché, borne inférieure, borne supérieure)
	Si borne inférieure est égale à borne supérieure:
		L'élément n'est pas dans le tableau. On retourne une valeur particulière. (-1 ?)
	Sinon
		On défini milieu par : (borne inférieure + borne supérieure) / 2
		Si tableau à l'élément milieu est égal au nombre recherché:
			On retourne la valeur milieu.
		Sinon Si tableau à l'élément milieu est supérieur au nombre recherché:
			On retourne la Fonction dichotomique en envoyant:
			- milieu + 1 pour la borne inférieure
			- la borne supérieure
		Sinon Si tableau à l'élément milieu est inférieur au nombre recherché:
			On retourne la Fonction dichotomique en envoyant:
			- La borne inférieure
			- milieu - 1