G4 – Recherche dichotomique dans un tableau trié

Le problème à résoudre

Solution proposée par une personne A

Algorithme : Recherche d'une valeur dans un tableau

1 - Commencer avec le premier élément du tableau.
2 - Comparer la valeur d'un élément du tableau avec la valeur recherchée :
3 - si les deux nombres sont identiques, alors afficher 'Vrai' et arrêter la recherche.
4 - sinon passer à l'élément suivant du tableau et recommencer à l'étape 2 tant que l'on n'a pas atteint le dernier élément du tableau.
5 - Après avoir atteint le dernier élément du tableau, afficher 'Faux'

Ecrire le programme correspondant à cet algorithme, en langage Python.

Solution proposée par une personne B

def recherche_B(tableau, n):
    """ Cherche la valeur 'n' parmi celles de 'tableau'."""

    tableau.sort()
    index = 0
    while tableau[index] < n and index < len(tableau):
        index += 1
    if tableau[index] == n:
        return True
    return False

Téléchargement d’un fichier : fonction écrite en langage Python

Ecrire l’algorithme correspondant à ce programme écrit en langage Python.

Evaluation et comparaison du coût temporel de ces deux solutions