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

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 ⭐ ⭐ ⭐ ⭐
Python
1
def recherche_dichotomique(lst, val) :
Code à trous ⭐ ⭐ ⭐
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 ⭐ ⭐
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 ⭐
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