Dichotomie

https://colab.research.google.com/drive/1ByJPMTl8Hk0yViq_3ZgdeVXcAgN3PbBQ?usp=sharing

Recherche Séquentielle :

Ecrivons une fonction qui recherche une valeur val dans un tableau tab. La fonction doit renvoyer True si la valeur est présente False si elle est absente.

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

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

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)