Un petit test aura d’ailleurs lieu mardi 9 février dans l’esprit de ces questions préparées en distanciel.

On revient sur le travail sur la dichotomie donné début janvier.

Nathan (merci) code pour nous 🙂

Dichotomie et complexité, statistiques

Le sujet donné début janvier :

Les statistiques sur un tableau de trié de taille 42 donnent une moyenne de plus de 5 coups pour la recherche dichotomique. Pas étonnant, quand on sait que :

donc

La complexité de la recherche dichotomique sur un tableau trié de taille étant en .

Le code en cliquant ci-dessous…

from random import randint

def tab_alea_trie(n = 42, p = 100):
    tab = [randint(0, p) for i in range(n)]
    tab.sort()
    return tab
#print(tab_alea_trie(12 , 5))

def rech_dicho(L, val):
    c = 0
    g = 0
    d = len(L) - 1
    
    while g <= d :
        c += 1
        m = (g + d) //2
        if L[m] == val:
            return m, c
        elif L[m] > val:
            d = m-1
        else :
            g = m+1

    return -1, c
m = 0

for i in range(1000):   
    L = tab_alea_trie()
    val = randint(0, 100)
    m += rech_dicho(L, val)[1]
    #print(L)

from math import log
print("Une moyenne de", m / 1000)
print("A comparer avec le log_2(42) :", log(42, 2))