Connexion élèves

Choisir le(s) module(s) à installer :

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):
	flag = False, -1
    for i in range(len(tab)):
        if tab[i] == valeur:
            flag = True, i
    
    return flag			# renvoi du flag
    		

Mais comme il existe en Python une méthode pour déterminer l'indice d'une valeur dans un tableau, on peut également faire une recherche par valeur :


def recherche_sequentielle(tab: list, valeur: int)->(bool, int):
	flag = False , -1
	for element in tab:
        if element == valeur:
            flag = True, tab.index(element)

    return flag
    		

Pour finir il peut sembler plus judicieux d'utiliser une boucle while car on ne sait pas quand l'élément recherché va être trouvé... :


def recherche_sequencielle_while(L: list,n: int)-> (bool,int):
    i=0
    while i ‹	len(L)-1 and L[i]!=n: # parcours du tableau jusqu'à avoir trouvé l'élément (ou atteint l'extrémité du tableau)
        i=i+1

    if i==len(L)-1 and L[i]!=n: #au sortir de la boucle, si on est à l'extrémité du tableau deux cas, soit l'élément cherché est le dernier soit on ne l'a pas trouvé
        return False, -1

    return True, i
    		

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
    flag = (False,-1)					# initialisation du drapeau
    
    while g<=d and flag[0]==False:                    # tant que la "zone de recherche" dans le tableau n'est pas réduite à un seul élément et que l'élément n'est pas trouvé
        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,
            flag = (True, m)          # le drapeau est modifié à True et cet l'indice trouvé.
        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 flag                # renvoi du drapeau