C17.1 : Recherche dans une liste
Position du problème
On dispose d'une liste d'entiers et d'un nombre entier.
On souhaite programmer une fonction qui permet de connaitre la position du nombre dans la liste s'il y est.
L'objectif de cette activité est d'étudier plusieurs algorithmes.
Toutes les fonctions pourront être testées avec le programme principal suivant :
L1 = [2, 8, 12, 15]
print(recherche(1, L1) == -1)
print(recherche(2, L1) == 0)
print(recherche(7, L1) == -1)
print(recherche(8, L1) == 1)
print(recherche(15, L1) == 3)
print(recherche(20, L1) == -1)Recherche séquentielle dans une liste non triée
A faire : Compléter la fonction du programme ci-dessous :
def recherche_seq(E, L):
'''
Recherche un élément dans une liste d'entiers.
Renvoie la position de la première occurrence l'élément s'il est présent dans la liste.
Renvoie -1 si l'élément n'est pas présent dans la liste.
param L : (list) une liste d'entiers
param E : (int) un entier
return : (int) position de l'entier ou -1
'''
# partie à compléter
# ----- programme principal -----
L1 = [2, 8, 12, 15]
print(recherche_seq(1, L1) == -1)
print(recherche_seq(2, L1) == 0)
print(recherche_seq(7, L1) == -1)
print(recherche_seq(8, L1) == 1)
print(recherche_seq(15, L1) == 3)
print(recherche_seq(20, L1) == -1)Recherche séquentielle dans une liste triée
On souhaite optimiser la fonction précédente lorsque la liste est triée.
A faire : Compléter la fonction du programme ci-dessous :
def recherche_seq_triee(E, L):
'''
Recherche un élément dans une liste d'entiers triée.
Renvoie la position de l'élément s'il est présent dans la liste.
Renvoie None si l'élément n'est pas présent dans la liste.
param L : (list) une liste d'entiers triés par ordre croissant
param E : (int) un entier
return : (int) position de l'entier ou -1
'''
# partie à compléterRecherche dichotomique
Dans cette partie, on s'intéresse encore à la recherche dans une liste triée, et on souhaite encore optimiser le programme du III.
Préambule
🖊️ Quelle est la meilleure stratégie pour trouver la bonne réponse au Jeu du plus/moins ?
Principe
Lorsque la liste dans laquelle la recherche se fait est triée, il est possible d'appliquer la même méthode que pour le jeu du Plus/Moins : la recherche dichotomique.
Écriture d'un algorithme
🖊️ Écrire la fonction basée sur la recherche par dichotomie.