Aller au contenu

Vers la recherche dichotomique⚓︎

Écrire une fonction recherche_dichotomique qui prend pour argument une liste lst triée et qui recherche une valeur val dans cette liste.

Si la valeur est trouvée, l'indice de la valeur est renvoyé. Sinon, on renvoie None.

Exemple d'utilisation

🐍 Script Python
>>> mylist = [2, 3, 6, 7, 11, 14, 18, 19, 24]
>>> recherche_dichotomique(mylist, 14)
5
>>> recherche_dichotomique(mylist, 2)
0
>>> recherche_dichotomique(mylist, 24)
8
>>> recherche_dichotomique(mylist, 1789)
>>>
Code à trous ⭐ ⭐ ⭐ ⭐
🐍 Script Python
1
def recherche_dichotomique(lst, val) :
Code à trous ⭐ ⭐ ⭐
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def recherche_dichotomique(lst, val) :
    indice_debut = ...
    indice_fin = ...
    while ... <= ... :
        ... = (... + ...) // ...    
        ... = lst[...]            
        if ... == ... :          
            return ...
        if valeur_centrale < ... :             
            ... = ... + ...
        else :
            ... = ... - ...
    return None
Code à trous ⭐ ⭐
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def recherche_dichotomique(lst, val) :
    indice_debut = ...
    indice_fin = ...
    while ... <= ... :
        indice_centre = (... + ...) // 2     
        ... = lst[...]            
        if valeur_centrale == ... :          
            return ...
        if valeur_centrale < ... :             
            ... = ... + 1
        else :
            ... = ... - 1
    return None
Code à trous ⭐
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def recherche_dichotomique(lst, val) :
    indice_debut = ...
    indice_fin = ...
    while indice_debut <= ... :
        indice_centre = (... + ...) // 2     
        valeur_centrale = lst[...]            
        if valeur_centrale == ... :          
            return indice_centre
        if valeur_centrale < ... :             
            indice_debut = ... + 1
        else :
            indice_fin = ... - 1
    return None