Aller au contenu

Vers l'algorithme de dichotomie⚓︎

Exemple d'utilisation :

🐍 Script Python
>>> tab = [1, 5, 7, 9, 12, 13]
>>> recherche_dichotomique(tab, 12)
True
>>> recherche_dichotomique(tab, 17)
False
Code à trous, newbie version
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def recherche_dichotomique(tab, val) :
    '''
    renvoie True ou False suivant la présence de la valeur val dans le tableau trié tab.
    '''
    i_debut = ...
    i_fin = ...
    while ... <= ... :
        i_centre = (... + ...) // 2     
        val_centrale = tab[...]         
        if val_centrale == val:              
            return ...
        if val_centrale < val:                
            i_debut = ... + 1            
        else :
            i_fin = ... - 1
    return False
Code à trous, regular version
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def recherche_dichotomique(tab, val) :
    '''
    renvoie True ou False suivant la présence de la valeur val dans le tableau trié tab.
    '''
    i_debut = ...
    i_fin = ...
    while ... <= ... :
        i_centre = ...   
        val_centrale = ...         
        if ... == ... :              
            return ...
        if ... < ...:                
            i_debut = ...        
        else :
            i_fin = ...
    return False
Code à trous, expert version
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def recherche_dichotomique(tab, val) :
    '''
    renvoie True ou False suivant la présence de la valeur val dans le tableau trié tab.
    '''
    ... = ...
    ... = ...
    while ... <= ... :
        ... = ...   
        ... = ...         
        if ... == ... :              
            return ...
        if ... < ...:                
            ... = ...         
        else :
            ... = ...
    return False
Code à trous, God version
🐍 Script Python
1
2
def recherche_dichotomique(tab, val) :
    ...

Pour tester :

🐍 Script Python
>>> tab = [1, 5, 7, 9, 12, 13]
>>> recherche_dichotomique(tab, 12)
True
>>> recherche_dichotomique(tab, 17)
False