Recherche dichotomique dans un tableau trié

https://colab.research.google.com/drive/1Gbz25OVKrGYRu6A5G-LmRzZ7sCKV4i2P?usp=sharing

Nous allons d’abord faire une fonction qui permet de chercher une valeur dans une table et si une valeur n’est pas inclus dans la table, alors la fonction est fausse

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

Une recherche dichotomique permet de trouver une valeur en divisant la table par deux. par exemple je cherche un nombre entre 1 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.

Nous allons faire une fonction dichotomique

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

Nous allons ensuite comparer le temps que prend la machine si jamais on lui demande de chercher un nombre dans une liste

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)

Nous remarquons que la machine ne peut pas supporter cette comparaison car la table est bcp trop grande

ln est une variable qui permet de chercher la puissance de deux par exemple pour diviser un entier

ex: ln(2048)/ln(2) = 11 le résultat est la puissance de 2