Dichotomie

INTRODUCTION:

JEU:

Je choisis un nombre entre 1 et 100. L’objectif est de trouver quel est ce nombre.

La meilleure stratégie pour résoudre ce problème est de « couper en deux » à chaque fois l’intervalle d’étude. On commence à 50, puis 75 ou 25 etc.

Cependant, si je propose un nombre de départ comme 90, la probabilité que le nombre choisi se trouve entre 90 et 100 est réduite, en revanche s’il l’est, cela représente un gros avantage car le nouvel intervalle est très réduit.

Pour conclure, la stratégie optimale est de diviser en deux à chaque étape l’intervalle d’étude. On appelle cela une méthode par dichotomie, du grec ancien διχοτομία, dikhotomia (« division en deux parties »).

La méthode de dichotomie fait partie des méthodes dites « diviser pour mieux régner« .

1. Recherche séquentielle

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

Dans cette fonction, l’ordinateur va regarder chaque valeur du tableau une à une afin de trouver la valeur correspondante. Si la valeur ne se trouve pas dans le tableau, la fonction affichera False.

2.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

Dans cette fonction, il est nécessaire que la tableau soit un tableau trié.

On prend l’indice de départ ainsi que l’indice de fin. On introduit une boucle : tant que l’indice de départ est inférieur ou égal par rapport à l’indice de fin, alors l’indice du centre est égal à la somme de l’indice du début diviser par deux. Si la valeur demandée est égale à la valeur se trouvant à l’indice du centre de ton tableau, la fonction affichera True. En revanche si la valeur….