recherche dichotomique entiers

Bonjour,

J'essaie de programmer un algorithme de recherche dichotomique dans une liste d'entiers :

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

maliste = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];   def rech_dichot(liste, borne_inf, borne_sup, x):   borne_interm = (borne_sup + borne_inf)/2;     if liste[borne_sup] < x or liste[borne_inf] > x: #si l'entier recherche n'est pas dans la liste return False; if liste[borne_interm] == x: return True; else:   if maliste[borne_interm] > x: rech_dichot(liste, borne_inf, borne_interm-1, x); else: if maliste[borne_interm] < x: rech_dichot(liste, borne_interm + 1, borne_sup, x); else: return False;     nbre_rech = input("Veuillez rentrer l'entier recherche : ");   print rech_dichot(maliste, 0, len(maliste)-1, int(nbre_rech));

---

J'ai utilisé une fonction recursive, je pense avoir optimisé pas mal le code, mais si vous voyez une amélioration possible n'hésitez pas à me le signaler.

Le problème c'est que si je rentre l'entier 2 par ex dans la console, la fonction me renvoie "none" alors que si je rentre l'entier 10 elle me renvoie "True". J'ai bien cherché mais je ne voit pas d'où ça peut venir. Pourriez-vous me mettre sur la voie svp ?

Merci

Salut,

On suppose que tu ne peux pas faire :

Code:

---

1 2	print x in maliste

---

Le problème de ton code c'est que :

Code:

---

1 2 3

if liste[borne_interm] == x: return True

---

1.- borne_interm n'est pas un entier dans un très grand nombre de cas ;

2.- le return ne renvoie pas à l'appel initial de la fonction mais à l'appel récursif qui se poursuit jusqu'à épuisement des nombres de la liste.

Dans ta liste, seul le nombre 10 est trouvé tout de suite (borne_intrem == 10) et dans ce cas le return renvoie à l'appel initial.

Tu peux aussi simplifier ta manipulation de liste.

exemple :

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

maliste = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]   def rech_dichot(l, x): is_present = False if x < l[0] or x > l[-1]: return False   while 1: mid = int(l[0] + ((l[-1] - l[0]) / 2)) if x == mid: is_present = True break elif x > mid: l = [n for n in l if n >= mid] else: l = [n for n in l if n <= mid] if len(l) < 3: is_present = x in l break else: rech_dichot(l, x)   return is_present     for i in maliste: print "%s in maliste : %s" % (i, rech_dichot(maliste, i))

---

Devrait être encore simplifié mais il est tard.

Bonjour,

Il est intéressant d'examiner le code du module bisect.py livré avec Python.

Voir aussi mon tuto comme source d'inspiration: j'ai fait une fonction de recherche par dichotomie qui utilise les mêmes fonctions comp et key que la méthode sort() et la fonction sorted():

http://python.jpvweb.com/mesrecettes...?id=dichotomie

Tyrtamos

Je vous remercie beaucoup je vais étudier ça ce soir, je vous tien au courant

Bonjour.

Un petit conseil rapide à Joe_Dupont.

Au lieu du code suivant...

Code:

---

1 2 3 4 5 6 7

if liste[borne_sup] < x or liste[borne_inf] > x: #si l'entier recherche n'est pas dans la liste return False; if liste[borne_interm] == x: return True; else: ...

---

..., tu devrais utiliser :

Code:

---

1 2 3 4 5

if liste[borne_inf] <= x <= liste[borne_sup]: Tu tries... else: return False

---

Personnellement, j'utiliserais même :

Code:

---

1 2 3 4 5

if liste[borne_inf] <= x <= liste[borne_sup]: Tu tries et renvoie True si cela marche et rien sinon.   return False

---

Autre remarque : les points-virgules en fin de ligne ne servent à rien !