Dichotomie

# liste au hasard pour les tests
from random import randint
L = [ randint(1,100) for j in range(30) ]
#tri de la liste :
L.sort()

def dicho(L,x) :
    debut, fin = 0, len(L)-1
    while debut <= fin :
        milieu = (debut+fin)//2
        if x == L[milieu] : return milieu
        elif x < L[milieu] : fin = milieu-1
        else : debut = milieu+1
    return -1 # cas x absent de L
    
    
##### test ######

print(L)
x = int(input('Entrez un entier naturel : '))
print()

print('Recherche par dichotomie.')
r=dicho(L,x)
if r != -1 : print("Elément trouvé à l'indice :", r,'.')
else : print('Elément absent.')
print()

print('Recherche par fonction builtin pour contrôle.')
for i, y in enumerate(L) :
    if y == x : print("Elément présent à l'indice ", i)

On pourra également chercher à programmer une version récursive de la recherche par dichotomie.

Avec une liste de 8 éléments.

La liste L est [l₀, l₁, ..., l₇ ].

Supposons que l'on cherche l'élément maximal de L avec l₀ ≤ l₁ ≤ ... ≤ l₆ < l₇. On recherche donc l'élément x=l₇.

Initialisation : debut=0, fin=7.

1. Étape 1. debut=0, fin=7. milieu=3, L[3]<x.
2. Étape 2. debut=4, fin=7. milieu=5, L[5]<x.
3. Étape 3. debut=6, fin=7. milieu=6, L[6]<x.
4. Étape 4. debut=7, fin=7. milieu=7, L[7]==x.

Il a donc fallu 4 étapes pour trouver une occurrence de x. Or blog(8)+1=blog(2³)+1=3+1=4.

Remarque. Si on cherche un élément x> L[7], la boucle de l'étape 4 ne permet pas de conclure, mais on ne rentrera toutefois pas une fois de plus dans la boucle puisqu'on aura debut>fin (condition du while non respectée). On aura donc le même nombre d'étapes si l'on appelle, comme suggéré dans l'énoncé, 'étape' une exécution du contenu de la boucle.

Avec une liste de longueur n=2^k éléments

Supposons comme précédemment que la liste contient des nombres distincts et que l'on cherche l'élément x de valeur maximale (donc d'indice 2^k-1 dans la liste).

1. Étape 1. debut=0, fin=2^k-1, milieu=2^k-1-1, L[2^k-1-1]<x.
2. Étape 2. debut=2^k-1, fin=2^k-1, milieu=2^k-2+2^k-1-1, L[2^k-2+2^k-1-1]<x.
3. Étape 3. debut=2^k-2+2^k-1, fin=2^k-1, milieu=2^k-3+2^k-2+2^k-1-1, L[2^k-3+2^k-2+2^k-1-1]<x.
4. Étape 4. debut=2^k-3+2^k-2+2^k-1, fin=2^k-1, milieu=2^k-4+2^k-3+2^k-2+2^k-1-1, L[2^k-4+2^k-3+2^k-2+2^k-1-1]<x.
5. ...
6. Etape j. \[ \text{debut} = \sum_{i=1}^{j-1} 2^{k-i}\] soit (progression géométrique... calculer 2*debut-debut=debut) \[ \text{debut} = 2^{k}-2^{k-(j-1)}\] fin est toujours égal à 2^k-1 et \[ \text{milieu}= \sum_{i=1}^{j} 2^{k-i}-1\]
7. ...
8. Etape k+1. \[ \text{debut} = \sum_{i=1}^{k+1-1} 2^{k-i}\] soit \[ \text{debut} = 2^{k}-1\] fin=2^k-1 et cette étape permet de conclure.

On a donc eu besoin de k+1= blog( 2^k)+1=blog(n)+1 étapes.

On remarquera qu'une étape nécessite en général un test == et un test <. Ici la dernière étape ne nécessitait qu'un seul des deux tests, mais les deux peuvent avoir lieu (cas de la recherche d'une valeur strictement plus grande que le maximum de la liste). On peut donc avoir besoin de 2(blog(n)+1) tests (== ou <) dans la recherche d'un élément dans la liste.

Pour établir que blog(n)+1 étapes suffisent, on va utiliser le fait que partant d'une liste de longueur m, on aboutit à une liste de longueur au plus m//2.

Soit L une liste de longueur n.

1. Avec l'étape 1, on réduit la recherche à une liste de taille au plus n//2.
2. Avec l'étape 2, on réduit la recherche à une liste de taille au plus n//(2²).
3. Avec l'étape 3, on réduit la recherche à une liste de taille au plus n//(2³).
4. ...
5. A l'étape j, on réduit la recherche à une liste de taille au plus n//(2^j).
6. ...
7. A l'étape blog(n), on réduit la recherche à une liste de taille au plus n//(2^blog(n)).

Par définition de blog(n), on a n//(2^blog(n)) ≤1. Il ne reste donc qu'au plus un élément à tester après cette étape blog(n). On aura donc terminé à l'étape suivante.

blog(n)+1 étapes suffisent donc toujours.

Calcul direct des deux nombres d'étapes

Dans les deux cas, il s'agit de calculer blog(n)+1. Rappelons que blog(n) se calcule facilement par un petit programme python :

def blog(x) :
    n = 0
    while x>1 :
        x/=2
        n+=1
    return n
    
    
print('Pop française : ', blog(65*10**6)+1 )
print('Pop mondiale : ', blog(7*10**9)+1)

ce qui donne :

Pop française :  27
Pop mondiale :  34

Comparer ces nombres aux nombres obtenus dans la recherche « naïve » de début de cours, cela devrait vous permettre de comprendre l'efficacité d'un algorithme présentant une complexité en log(n)...

Calcul du second nombre d'étapes à partir du premier.

\( \frac{7 \times 10^9}{65 \times 10^6} \approx 107,69 \)

La population mondiale est plus de 107 fois la population française.

Comme \( \log_2(ab) = \log_2(a) + \log_2(b) \), on peut écrire : \[ \log_2( \text{pop mondiale} ) \approx \log_2( 107,69 ) + \log_2( \text{pop française}) \]

Comme \( \log_2( 107.69) \approx 6.75 \), on comprend maintenant pourquoi le nombre d'étapes augmente aussi peu entre une recherche dans un annuaire de 65 millions d'entrées et une recherche dans un annuaire de 7 milliards d'entrées.