Dichotomie

https://colab.research.google.com/drive/1zuM0K-AIPZoLF7xCL1vBT2uhOlPjdMeW#scrollTo=Asrq-pcaUD8N&uniqifier=1

Recherche séquentielle

Ecriture d’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.

Test :

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

Correction :

–> Cet algorithme n’est pas optimal puisque l’on doit passer par chaque valeur pour trouver la bonne, alors qu’elles sont déjà triées. Cela aurait été plus pertinent si les valeurs étaient déjà triées.

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

Recherche dichotomique

Test :

–> Par exemple, une personne pense à un nombre entre 0 et 100 :

On va demander si ce nombre correspond à 50, et la personne va nous dire si c’est plus ou moins (ou 50, dans ces cas-là l’algorithme s’arrête là).

Si le nombre est supérieur :

• on va demander le milieu de 100 et 50, autrement dit (100 + 50) // 2 = 75

Si le nombre est inférieur :

• on va simplement demander la moitié de 50, c’est-à-dire 50 // 2 =25

Et ainsi de suite jusqu’à trouver le « juste prix » !

def dichotomie(tab,val):
  début = tab(0)
  if m>début:
    début = (len(tab)+début)//2
  elif m>début:
    début = début//2
  else:
    return True

Correction :

–> Tant que le nombre de départ est inférieur ou égal au nombre de fin :

• le nombre que l’on cherche est égal au (nombre de départ + celui de fin) // 2
• ainsi si la valeur que l’on cherche est égale à m dans tab, le programme s’arrête et renvoie True
• si valeur que l’on cherche est supérieure à m dans tab, le nombre de départ devient m + 1
• sinon, le nombre de fin devient m – 1

etc, jusqu’à ce que le programme tombe sur le nombre ou renvoie False.

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

Tests :

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

rechercher(tab,99999999)

import timeit
tab = [i for i in range(1000000)]
%timeit rechercher(tab,999999)

Correction :

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)