C17.1 : Recherche dans une liste

Position du problème

On souhaite écrire une fonction recherche(liste:list, n:int)->int qui prend une liste d'entiers et un entier en paramètres et renvoie la position de l'entier dans la liste s'il y est, ou -1 s'il n'y est pas.

L'objectif de cette activité est d'étudier plusieurs algorithmes.

Toutes les fonctions recherche écrites pourront être testées avec la suivante :

def test_fct_recherche():
    L1 = [2, 8, 12, 15]
    assert recherche(1, L1) == -1
    assert recherche(2, L1) == 0
    assert recherche(7, L1) == -1
    assert recherche(8, L1) == 1
    assert recherche(15, L1) == 3
    assert recherche(20, L1) == -1
    print('Les tests sont validés')

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

def test_fct_recherche_seq():
    L1 = [2, 8, 12, 15]
    assert recherche_seq(1, L1) == -1
    assert recherche_seq(2, L1) == 0
    assert recherche_seq(7, L1) == -1
    assert recherche_seq(8, L1) == 1
    assert recherche_seq(15, L1) == 3
    assert recherche_seq(20, L1) == -1
    print('Les tests sont validés')

# ----- programme principal -----
test_fct_recherche_seq()
Afficher la correction 
def recherche_seq_v1(E, L):
    '''
    Recherche un élément dans une liste triée d'entiers.
    Renvoie la position de la première occurrence de 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
    '''
    i = 0
    val = L[0]
    while i < len(L)-1 and L[i] != E:
        i = i + 1
    if L[i] == E:
        reponse = i
    else:
        reponse = -1
    return reponse

def recherche_seq_v2(E, L):
    '''
    Recherche un élément dans une liste triée d'entiers.
    Renvoie la position de la première occurrence de 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
    '''
    for i in range(len(L)):
        if E == L[i]:
            return i
    return -1

# ----- Fct test -----
def test_fct_recherche_seq_v1():
    L1 = [2, 8, 12, 15]
    assert recherche_seq_v1(1, L1) == -1
    assert recherche_seq_v1(2, L1) == 0
    assert recherche_seq_v1(7, L1) == -1
    assert recherche_seq_v1(8, L1) == 1
    assert recherche_seq_v1(15, L1) == 3
    assert recherche_seq_v1(20, L1) == -1
    print("Les tests pour 'test_fct_recherche_seq_v1' sont validés")

def test_fct_recherche_seq_v2():
    L1 = [2, 8, 12, 15]
    assert recherche_seq_v2(1, L1) == -1
    assert recherche_seq_v2(2, L1) == 0
    assert recherche_seq_v2(7, L1) == -1
    assert recherche_seq_v2(8, L1) == 1
    assert recherche_seq_v2(15, L1) == 3
    assert recherche_seq_v2(20, L1) == -1
    print("Les tests pour 'test_fct_recherche_seq_v2' sont validés")

# ----- programme principal -----
test_fct_recherche_seq_v1()
test_fct_recherche_seq_v2()

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éter
Afficher la correction 
def recherche_seq_triee_v1(E, L):
    '''
    Recherche un élément dans une liste triée d'entiers.
    Renvoie la position de 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 triés par ordre croissant
    param E : (int) un entier
    return : (int) position de l'entier ou -1
    '''
    i = 0
    val = L[0]
    while i < len(L)-1 and L[i] < E :
        i = i + 1
    if L[i] == E:
        reponse = i
    else:
        reponse = -1
    return reponse

def recherche_seq_triee_v2(E, L):
    '''
    Recherche un élément dans une liste triée d'entiers.
    Renvoie la position de 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 triés par ordre croissant
    param E : (int) un entier
    return : (int) position de l'entier ou -1
    '''
    for i in range(len(L)):
        if L[i] == E:
            return i
        elif L[i] > E:
            return -1
    return -1

# === Programme principal ===
L1 = [2, 8, 12, 15]
print('==== v1 ====')
print(recherche_seq_triee_v1(1, L1) == -1)
print(recherche_seq_triee_v1(2, L1) == 0)
print(recherche_seq_triee_v1(7, L1) == -1)
print(recherche_seq_triee_v1(8, L1) == 1)
print(recherche_seq_triee_v1(15, L1) == 3)
print(recherche_seq_triee_v1(20, L1) == -1)
print('==== v2 ====')
print(recherche_seq_triee_v2(1, L1) == -1)
print(recherche_seq_triee_v2(2, L1) == 0)
print(recherche_seq_triee_v2(7, L1) == -1)
print(recherche_seq_triee_v2(8, L1) == 1)
print(recherche_seq_triee_v2(15, L1) == 3)
print(recherche_seq_triee_v2(20, L1) == -1)

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

Afficher la correction

• Détail du principe sur un exemple : lien vers un fichier pdf

Écriture d'un algorithme

🖊️ Écrire la fonction recherche_dichotomique(E,L) basée sur la recherche par dichotomie.

Afficher la correction 
def recherche_dichotomique(E,L):
    '''
    Recherche une valeur dans une liste triée.
    Renvoie la position de la valeur si elle est dans la liste.
    Renvoie -1 si la valeur n'est pas dans la liste.
    param E: (int) un entier
    param L: (list) une liste triée d'entiers
    return (int) : position de E dans L ou -1
    '''
    a = 0
    b = len(L)-1
    m = (a + b) //2
    while b - a > 0 and E != L[m]:
        if E < L[m]:
            b = m-1
        else:
            a = m+1
        m = (a + b) //2
    if E == L[m]:
        return m
    else :
        return -1

# ----- Fct test -----
def test_fct_recherche_dichotomique():
    L1 = [2, 8, 12, 15]
    assert recherche_dichotomique(1, L1) == -1
    assert recherche_dichotomique(2, L1) == 0
    assert recherche_dichotomique(7, L1) == -1
    assert recherche_dichotomique(8, L1) == 1
    assert recherche_dichotomique(15, L1) == 3
    assert recherche_dichotomique(20, L1) == -1
    print('Les tests sont validés')

# ----- programme principal -----
test_fct_recherche_dichotomique()

Pour aller plus loin

Lien : Recherche dichotomique dans une liste triée