Recherche dichotomique - Correction

Correction de la fiche

La fiche corrigée est ici.

Codage Python

Recherche séquentielle

Pour avoir l'indice de la valeur recherchée, le plus logique est donc de faire un parcours par indice du tableau :

def recherche_sequentielle(tab: list, valeur: int)->(bool, int):
    for i in range(len(tab)):
        if tab[i] == valeur:
            return True, i
    
    return False, -1				# "-1" est l'entier signifiant "pas trouvé"
    		

Recherche dichotomique

def recherche_dicho(tab: list, valeur: int)->(bool, int):

    g = 0                           # g = indice du premier élément du tableau
    d = len(tab)-1                  # d = indice du dernier élément

    while g<=d :                    # tant que la "zone de recherche" dans le tableau n'est pas réduite à un seul ou deux élément(s)
        m = (g+d)//2                # calcul de l'indice de l'élément "au milieu"

        if tab[m] == valeur:        # si l'élément à cet indice est égal à la valeur recherchée,
            return True, m          # alors on renvoie True et cet indice.
        else:                       # Sinon,
            if valeur < tab[m]:     # si la valeur recherchée est PLUS PETITE que l'élément à l'indice m,
                d = m - 1           # alors on poursuit la recherche dans la partie GAUCHE
            else:                   # sinon ( donc si la valeur recherchée est PLUS GRANDE ),
                g = m + 1           # alors on poursuit la recherche dans la partie DROITE

    return False, -1                # si la "zone de recherche" a été réduite à un seul élément, c'est que la valeur n'est pas présente dans le tableau