Recherche dichotomique

La recherche par dichotomie ou communément appelé recherche dichotomique est un algorithme qui nous permet de trouver la position précise d’un élément présent dans un tableau trié. Cet algorithme va comparer l’élément avec la valeur de la case présente au milieu du tableau : si les valeurs sont égales, la tâche est accomplie sinon on recommence dans la moitié du tableau pertinente.

Par exemple,

A et B jouent au jeu suivant : A choisit un nombre entre 1 et 20, et ne le communique pas à B, B doit trouver ce nombre en posant des questions à A dont les réponses ne peuvent être que « Non, plus grand », « Non, plus petit » ou « Oui, trouvé ». B doit essayer de poser le moins de questions possible.

Une stratégie pour B est d’essayer tous les nombres, mais il peut aller plus rapidement comme le montre le scénario suivant :

A choisit 14 et attend les questions de B :

• B sait que le nombre est entre 1 et 20 ; au milieu se trouve 10 (ou 11), B demande donc : « Est-ce que le nombre est 10 ? ». A répond « Non, plus grand ».
• B sait maintenant que le nombre est entre 11 et 20 ; au milieu se trouve 15 (ou 16), il demande donc : « Est-ce que le nombre est 15 ? » A répond « Non, plus petit »
• Et ainsi de suite : « Est-ce 12 ? » (12 < 12,5 < 13), « Non, plus grand », « Est-ce 13? » (13 < 13,5 < 14), « Non, plus grand », « Est-ce bien 14 ? », « Oui, trouvé »
• B a trouvé le nombre choisi par A en seulement 5 questions.

Il y a deux types de recherches, l’une où cela se passe dans une séquence et l’autre se passe dans un tableau avec d’innombrables valeurs :

• Recherche Séquentielle
• Recherche Dichotomique

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

Mais nous pouvons aussi comparer toutes les valeurs présentes grâce à la comparaison :

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)