Recherche dichotomique dans un tableau trié

Recherche séquentielle

def rechercher(tab,val):
    for nombre in tab:
        if nombre==val:
            return True
    return False   

Recherche dichotomique

def dichotomie(tab,val):
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = (debut + fin) // 2
        if val== tab[m]:
            return True
        if val > tab[m]:
            debut = m + 1
        else:
            fin = m - 1
    return False

comparaison

import time

tab=[i for i in range(100000000)]

debut1=time.time()
rechercher(tab,10000000)
duree1=time.time()-debut1
print(duree1)

debut2=time.time()
dichotomie(tab,10000000)
duree2=time.time()-debut2
print(duree2)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *