Discussion :

[goomie]

voici une fonction qui effectue une recherche dichotomique sur une liste d element exemple la liste ['a','b','c','d','e','f','g'] etc nb il faut que la liste soit trie le recherche dichotomique n est efficace qu cette condition

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
 
 
 
def dicho(chaine,recherche):
    """recherche un element dans une liste d element"""
    i=len(chaine)
    flag=False
    while(i!=1):
        i/=2
        if recherche>chaine[i]:
            if recherche==chaine[i]:
                flag= True
 
            else:
                chaine=chaine[i:]
                i=len(chaine)
                ##print chaine
        else:
            if recherche==chaine[i]:
                flag=True
            else:
                chaine=chaine[:i]
                i=len(chaine)
                ##print chaine
    return flag
##deux  exemples dicho(list("chaine"),"a");dicho([1,2,3,4,5,6],9)

[gorgonite]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
if recherche>chaine[i]:
            if recherche==chaine[i]:

y aurait pas un problème là ?

comment peut-on être égal à quelque chose si l'on est strictement plus grand ?


ensuite, pourquoi attendre que i soit égale à 1 ?
y a moyen de sortir plus vite de la boucle... sans forcemment alourdir le test de terminaison

[goomie]

tu sais l on peu resoudre un probleme en etantr ilogique pour ma par j ai tester cette fonctrion et je t assure que ca marche pour peu que l on y donne les bonne valeur a

[goomie]

je corrige le code effectivement il y avait une erreur le test n etait jamais verifie et voila maintenant le nouveau code quand au test de la boucle while on peu s assurrer d avoir une lettre dans une liste que si l on parcourue toutla liste sauf si on troiuve la lettre avant c est pour ca que j ai rajouter un break si le test de comparaison est positif voila merci a toi guigui pour ton aide precieuse

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
 
def dicho(chaine,recherche):
    """recherche un element dans une liste d element"""
    i=len(chaine)
    flag=False
    while(i!=1):
        i/=2
        if recherche>chaine[i]:
 
            chaine=chaine[i:]
            i=len(chaine)
        elif recherche==chaine[i]:
            flag= True##print chaine
            break
        else:
 
            chaine=chaine[:i]
            i=len(chaine)
                ##print chaine
    return flag

aa+

[Garulfo]

tu sais l on peu resoudre un probleme en etantr ilogique pour ma par j ai tester cette fonctrion et je t assure que ca marche pour peu que l on y donne les bonne valeur a

C'est clair que si tu donnes des valeurs pour que ton algorithme fonctionne, alors il fonctionne bien -_- C'est un peu idéaliste quand même. D'ailleurs visiblement tu as pu observer que tu l'avais mal testée.

[xcombelle]

On peut aussi utiliser le module bisect comme indique ci après http://code.activestate.com/recipes/54159/