XD blog

blog page

dichotomie


2013-12-01 Recherche dichotomique, récursive, itérative et le logarithme

Lorsqu'on décrit n'importe quel algorithme, on évoque toujours son coût, souvent une formule de ce style :

 O\left(n^u (\ln_2 n)^v\right)

u et v sont des entiers. v est souvent soit 0, soit 1. Mais d'où vient ce logarithme ? Le premier algorithme auquel on pense et dont le coût correspond au cas u=0 et v=1 est la recherche dichotomique. Il consiste à chercher un élément dans une liste triée. Le logarithme vient du fait qu'on réduit l'espace de recherche par deux à chaque itération. Fatalement, on trouve très vite l'élément à chercher. Et le logarithme, dans la plupart des algorithmes, vient du fait qu'on divise la dimension du problème par un nombre entier à chaque itération, ici 2.

La recherche dichotomique est assez simple : on part d'une liste triée T et on cherche l'élément v (on suppose qu'il s'y trouve). On procède comme suit :

C'est ce qu'illustre la figure suivante où a désigne le début de la liste, b la fin, m le milieu. A chaque itération, on déplace ces trois positions.

Voici une première implémentation en Python (version itérative) :

def recherche_dichotomique( element, liste_triee ):
    a = 0
    b = len(liste_triee)-1
    m = (a+b)//2
    while a < b :
        if liste_triee[m] == element :
            return m
        elif liste_triee[m] > element :
            b = m-1
        else :
            a = m+1
        m = (a+b)//2
    return a

Voici une seconde implémentation en Python (version récursive) :

def recherche_dichotomique_recursive( element, liste_triee, a = 0, b = -1 ):
    if a == b : 
        return a
    if b == -1 : 
        b = len(liste_triee)-1
    m = (a+b)//2
    if liste_triee[m] == element :
        return m
    elif liste_triee[m] > element :
        return recherche_dichotomique_recursive(element, liste_triee, a, m-1)
    else :
        return recherche_dichotomique_recursive(element, liste_triee, m+1, b)

L'ajout des parametrès a et b peut paraître un peu lourd. Voici une troisième implémentation en Python (toujours récursive) :

def recherche_dichotomique_recursive2(element, liste_triee):
    if len(liste_triee)==1 :
        return 0
    m = len(liste_triee)//2
    if liste_triee[m] == element :
        return m
    elif liste_triee[m] > element :
        return recherche_dichotomique_recursive2(element, liste_triee[:m])
    else :
        return m + recherche_dichotomique_recursive2(element, liste_triee[m:])

Il ne faut pas oublier m + sinon le résultat peut être décalé dans certains cas. Ensuite, cette version sera un peu moins rapide du fait de la recopie d'une partie de la liste.

Pour mieux comprendre les différences de ces algorithms, vous pouvez observer le déroulement de l'exécution sur PythonTutor.


Xavier Dupré