Recherche dichotomique dans un tableau trié

https://colab.research.google.com/drive/1U5xi-XDZd0nLkbX6hyPg9KE9XlZjoH9o?usp=sharing

I| Recherche séquentielle

Nous allons d’abord commencer à faire une fonction qui permet de chercher une valeur dans une liste et si une valeur est inclus dans la liste alors la fonction True sinon False .

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

II| Recherche dichotomique

Elle va nous permettre de trouver une valeur en divisant la table par deux. par exemple je cherche un nombre entre 0 et 100, je pense à 25 . 25 est plus petit que le milieu de 100, donc on divise encore par 2 et nous avons trouvé le nombre.

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):
  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

III | 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)