Ctrl+K

Rechercher

4. Rechercher#

Mis à jour : May 15, 2025, lecture : 17 minutes minimum, PhL.

# pour python<3.9
#from typing import list

4.1. Objectif du chapitre#

Ce chapitre présente des versions de deux algorithmes déjà connus pour rechercher si une valeur est présente ou non dans un ensemble de valeurs. Cet ensemble de valeurs est stocké dans un tableau (1D ou nD selon le type de valeurs).

Au delà de la question de la recherche de valeur dans un ensemble, ce chapitre permet :

  1. de construire des versions itératives et récursives d’un même algorithme,

  2. d’effectuer une analyse de complexité

  3. (\(\star\)) d’illustrer la preuve de terminaison et de correction de ces traitements.

Les algorithmes concernés sont :

  • la recherche séquentielle

  • la recherche dichotomique – lorsque les valeurs sont préalablement triées.

4.2. Recherche séquentielle#

4.2.1. Principes#

Objectif
Rechercher si une valeur apparaît ou non dans un tableau de valeurs
Répondre vrai si la valeur est dans le tableau, faux sinon

Hypothèse de départ
Il existe une relation de comparaison entre deux valeurs : égalité. - on la note ==
Aucune hypothèse sur les valeurs

Principe de la recherche séquentielle
Parcourir séquentiellement le tableau de valeurs et comparer à la valeur cherchée.

  • séquentiellement : “valeur après valeur” selon un ordre induit par les indices des valeurs dans le t

    • exemple : du début à la fin du tableau donc pour un ordre croissant des indices

  • parcours complet : de 0 à len(t)-1

  • parcours optimal : arrêt du parcours dès la valeur trouvée

Exemple pour la suite.

Un tableau de 10 entiers aléatoirement compris entre 0 et 10 va illustrer notre propos.

from random import randint, seed

n = 10
t = [0 for i in range(n)]

seed(2)
for i in range(n):
    t[i] = randint(0, n)
print(t)

[0, 1, 1, 5, 2, 10, 4, 4, 9, 3]

Rmq. seed(2) initialise de façon reproductible le générateur aléatoire (randint()) qui construit le tableau t. t est ainsi initialisé de façon identique à chaque exécution de cette cellule. Ce qui est commode pour des tests unitaires.

En-tête “modèle” de la fonction#

def rech_seq(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)'''

  • entrées :

    • val : la valeur à chercher – ici un int

    • tab : le tableau 1D qui contient les valeurs – ici un tableau 1D représenté par une liste python

    • dim : len(tab) le nombre de valeurs

  • sortie :

    • booléen : True ou False

Cet en-tête de fonction fixe certaines caractéristiques des paramètres du problème. En effet, la recherche s’effectue ici dans un ensemble représenté par un tableau et la valeur cherchée est un entier. Ces paramètres ensemble et valeur pourraient être différents : par exemple la recherche peut s’effectuer dans une liste de nombres flottants, une chaîne de caractères, un dictionnaire … Il faudrait alors modifier l’en-tête pour ces types de données.

Cet en-tête est donc un modèle d’en-tête pour une fonction de recherche. On peut voir le type des valeurs et la structure de stockage comme des paramètres de plus haut niveau d’abstraction de ce traitement. Ceci correspond à la notion de généricité ou de certaines formes de la notion d’héritage dans les langages (dits) objet.

Tests unitaires

Plusieurs versions de la fonction rech_seq() vont être étudiées par la suite. On illustrera le résultat de la première avec des print(). On préfère ensuite des tests unitaires avec le tableau t. On les définit dès maintenant.

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq(1, t, len(t)) == True
assert rech_seq(3, t, len(t)) == True
assert rech_seq(7, t, len(t)) == False

4.2.2. Algorithmes itératifs#

Algorithme avec parcours complet#

Principe du parcours séquentiel (dit) “naïf”:

  • On parcourt une à une toutes les valeurs tab[i] pour i = 0,.., dim-1

  • on compare à la valeur cherchée val

  • on met à jour une variable booléenne trouve qui marque la présence ou non de valdans tab

  • A la fin du parcours, trouve indique si vala été trouvée ou non

    • donc on initialise trouveà False avant de commencer le parcours

def rech_seq_for(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    version itérative avec parcours complet de tab'''
    trouve = False
    for i in range(dim):
        if tab[i] == val:
            trouve = True
    return trouve

  • Application (appel et print())

v = 1
print(v, "dans ", t, "?", rech_seq_for(v, t, len(t)))
v = 3
print(v, "dans ", t, "?", rech_seq_for(v, t, len(t)))
v = 7
print(v, "dans ", t, "?", rech_seq_for(v, t, len(t)))

1 dans  [0, 1, 1, 5, 2, 10, 4, 4, 9, 3] ? True
3 dans  [0, 1, 1, 5, 2, 10, 4, 4, 9, 3] ? True
7 dans  [0, 1, 1, 5, 2, 10, 4, 4, 9, 3] ? False

  • Tests unitaires.

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq_for(1, t, len(t)) == True
assert rech_seq_for(3, t, len(t)) == True
assert rech_seq_for(7, t, len(t)) == False

Commentaires.

  • Le parcours complet du tableau est d’autant moins efficace que le nombre de valeurs inutilement parcourues est important : valeur cherchée trouvée tôt dans ce parcours et/ou taille du tableau élevée.

  • D’un point de vue de complexité, on identifie un meilleur cas (valeur présente tôt) qui n’est pas traité différemment d’un pire cas (valeur absente).

  • C’est une faiblesse de cette première solution.

Algorithme avec un parcours optimal#

Même principe excepté :

  • la mise à jour de trouve permet d’arrêter le parcours dès que val a été trouvée

Voilà une première version qui découle de la construction avec for.

def rech_seq_while_v0(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    version itérative avec parcours optimal de tab : while et test d'arrêt supplémentaire'''
    trouve = False
    i = 0
    while i < dim and trouve == False:
        if tab[i] == val:
            trouve = True
        i = i + 1 
    return trouve

Tests unitaires.

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq_while_v0(1, t, len(t)) == True
assert rech_seq_while_v0(3, t, len(t)) == True
assert rech_seq_while_v0(7, t, len(t)) == False

La variable trouve n’est pas nécessaire comme l’illustre la version plus simple suivante.

def rech_seq_while(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    version itérative avec parcours optimal de tab : while'''
    i = 0
    while i < dim:
        if tab[i] == val:
            return True
        i = i + 1 
    return False

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq_while(1, t, len(t)) == True
assert rech_seq_while(3, t, len(t)) == True
assert rech_seq_while(7, t, len(t)) == False

Autre écriture de la condition du while où il faut être prudent : Attention à l’ordre des tests dans la condition de la ligne 4

Rappel : En python, l’opérateur logique and est paresseux. C-a-d. l’opérande de droite est évaluée si l’opérande de gauche est True.

  • Application : la condition de gauche protège l’évaluation de la condition de droite. Ici l’accès à une valeurs hors du tableau t.

def autre_rech_seq_while(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    version itérative avec parcours optimal de tab : while'''
    i = 0
   # ordre correct où la validité de l'indice est vérifiée avant de l'utiliser
    while i < dim and tab[i] != val:
        i = i + 1 
    if i < dim:
        return True
    else:
        return False

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert autre_rech_seq_while(1, t, len(t)) == True
assert autre_rech_seq_while(3, t, len(t)) == True
assert autre_rech_seq_while(7, t, len(t)) == False

L’inversion de la condition de répétition du while est maintenant incorrecte : l’appel pour une valeur absente conduit à traitement qui déborde du tableau `t``.

def aie(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    version itérative avec parcours optimal de tab : while'''
    i = 0
    # ordre incorrect qui va lever IndexError
    while  (tab[i] != val) and (i < dim):
        i = i + 1 
    if i < dim:
        return True
    else:
        return False

aie(11, t, len(t))

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[22], line 1
----> 1 aie(11, t, len(t))

Cell In[19], line 6, in aie(val, tab, dim)
      4 i = 0
      5 # ordre incorrect qui va lever IndexError
----> 6 while  (tab[i] != val) and (i < dim):
      7     i = i + 1 
      8 if i < dim:

IndexError: list index out of range

Ecriture équivalente avec une boucle for

La construction suivante permet le même traitement minimal au sein d’une boucle for

def rech_seq_for_ecourtee(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    version itérative avec parcours optimal de tab : for et return d'arrêt'''
    trouve = False
    for i in range(dim):
        if tab[i] == val:
            return True
    return trouve

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq_for_ecourtee(1, t, len(t)) == True
assert rech_seq_for_ecourtee(3, t, len(t)) == True
assert rech_seq_for_ecourtee(7, t, len(t)) == False

Remarque. Il est inutile d’utiliser l’instruction break.

Cas du tableau vide#

Ce cas extrême mérite souvent une attention particulière.

  • On convient qu’aucune valeur n’existe dans un tableau vide. Donc la recherche doit retourner False pour toute valeur.

  • Les versions avec la boucle for avec la borne len(t) s’adaptent “automatiquement” à ce cas grâce à la fonction range() – et retournent False.

  • En revanche, les écritures avec while demandent en général plus d’attention.

    • Dans rech_seq_while() :

    • la condition de répétition i < dim n’est pas satisfaite pour i == 0 et dim == 0,

    • et dans ce cas la valeur False est retournée, ce qui est correct.

On verra que l’analyse de la correction de cet algorithme confirme que cette écriture est bien correcte.

Pour la version suivante, le traitement du tableau se termine avec l’erreur IndexError: list index out of range

def rech_seq_while_2_faux(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    - version itérative avec parcours optimal de tab : while
    - erreur pour le tableau vide'''
    assert dim == len(tab)
    
    # autres cas
    i = 0
    while True:
        if tab[i] == val:
            return True
        if i == dim - 1: # le dernier élément de tab a été atteint et ne vaut pas val
            return False
        i = i + 1

L’ajout du traitement du cas particulier du tableau vide permet maintenant une exécution sans erreur de cette version.

def rech_seq_while_2(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    - version itérative avec parcours optimal de tab : while
    - traite le cas du tableau vide'''
    assert dim == len(tab)

    # cas du tableau vide
    if dim == 0:
        return False
    
    # autres cas
    i = 0
    while True:
        if tab[i] == val:
            return True
        if i == dim - 1: # le dernier élément de tab a été atteint et ne vaut pas val
            return False
        i = i + 1 

t_vide = []
res = rech_seq_while_2(1, t_vide, len(t_vide))

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq_while_2(1, t, len(t)) == True
assert rech_seq_while_2(3, t, len(t)) == True
assert rech_seq_while_2(7, t, len(t)) == False

4.2.3. Algorithme récursif#

La recherche séquentielle s’exprime aussi de façon récursive.

Principe

  • Récursion : Rechercher val dans tab de 0 à dim-1, c’est :

    1. regarder si val est en première position du tableau tab, cad. en tab[0],

    2. si c’est le cas, on a trouvé et on peut répondre : terminaison

    3. si ce n’est pas le cas, on recommence récursivement en 1. avec la partie restante de tab, cad. le sous-tableau “à droite” de la position testée.

  • En-tête adaptée à un traitement récursif :
    On va introduire g (pour gauche) pour désigner le premier indice de tab, cad. tab[g, dim[.

    • g == 0 pour le tableau complet

    • c’est cet indice g qui permet de parcourir séquentiellement le tableau lors des appels récursifs

On reprend la description précédente : Rechercher val dans tab[g, dim[ c’est :

  1. regarder si val est en première position du tableau tab, c-a-d. en tab[g],

  2. si c’est le cas, on a trouvé et on peut répondre : la récursion termine

  3. si ce n’est pas le cas, on recommence récursivement (en 1.) avec la partie de tab “à droite” de la première position, cad. avec le sous-tableau tab[g+1, dim[.

  • Terminaison : 2 cas

    1. on a trouvé val dans tab si tab[g] == val

    2. on n’a pas trouvé si g == dim le tableau tab a été entièrement parcouru sans succès.

  • Initialisation :

    1. g = 0 et dim ou len(tab) en python

Mise en oeuvre

On écrit le traitement récursif en 2 temps.

  1. La recherche récursive dans tab[g, dim[

    • On traite les terminaisons (return des lignes 4 et 6) avant l’appel récursif (avec le return de la ligne 8)

def rech_seq_rec_g(val: int, g: int, tab: list[int], dim: int) -> bool:
    '''recherche val dans tab[g, dim['''
    if g == dim: # fin du traitement séquentiel 
        return False
    if t[g] == val: # gagné
        return True
    else: # récursion sur 
        return rech_seq_rec_g(val, g+1, tab, dim)

  1. L’appel récursif principal, c-a-d. la recherche dans tab[0, dim[

  • L’initialisation des paramètres de la recherche récursive : c-a-d. ici g = 0.

def rech_seq_rec(val: int, tab: list[int], dim: int) -> bool:
    '''recherche si val est present dans tab (de longueur dim)
    - version récursive avec parcours optimal de tab 
    - traite le cas du tableau vide'''
    return rech_seq_rec_g(val, 0, tab, len(tab))

  • Ainsi la version récursive à un en-tête similaire à celle des versions itératives : 3 paramètres (la valeur, le nom du tableau et sa taille)

  • Vocabulaire. Cette fonction encapsule l’appel principal à la fonction récursive

v = 1
print(v, "dans ", t, "?", rech_seq_rec(v, t, len(t)))
v = 3
print(v, "dans ", t, "?", rech_seq_rec(v, t, len(t)))
v = 7
print(v, "dans ", t, "?", rech_seq_rec(v, t, len(t)))

1 dans  [0, 1, 1, 5, 2, 10, 4, 4, 9, 3] ? True
3 dans  [0, 1, 1, 5, 2, 10, 4, 4, 9, 3] ? True
7 dans  [0, 1, 1, 5, 2, 10, 4, 4, 9, 3] ? False

Reprenons les bonnes habitudes avec les test unitaires déjà utilisés pour les versions itératives. On ajoute dès maintenant le cas du tableau vide.

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq_rec(1, t, len(t)) == True
assert rech_seq_rec(3, t, len(t)) == True
assert rech_seq_rec(7, t, len(t)) == False
# tableau vide
assert rech_seq_rec(0, [], 0) == False

Warning

L’ordre du traitement des terminaisons (lignes 3 et 5) est important : ici l’accès t[g] est susceptible de lever une exception (débordement de tableau).

Remarques :

  • Quelle version de recherche séquentielle (parcours complet vs. minimal) correspond à l’écriture récursive ici proposée ?

    • Ecrire l’autre version de façon récursive.

4.3. Recherche dichotomique dans un tableau trié#

Dans le cas où les valeurs sont triées, on peut introduire un traitement plus efficace.
Ce traitement, par dichotomie, peut s’écrire de façon itérative ou récursive.
On va ainsi illustrer l’application du principe diviser pour régner.

4.3.1. Principes#

Objectif
Rechercher si une valeur apparait dans un tableau de valeurs triées
Répondre vrai si la valeur est dans le tableau, faux sinon

Hypothèse de départ
Les valeurs sont rangées de façon triée (on ne le dira jamais assez !)
par ordre croissant par exemple

Trions t pour continuer selon ces hypothèses.

# En attendant le chapitre suivant, utilisons les fonctions prédéfinies de python
t.sort()
print(t)

[0, 1, 1, 2, 3, 4, 4, 5, 9, 10]

Principe
Un algorithme diviser pour régner où chaque division réduit la recherche à un ensemble de taille moitié, l’autre ensemble n’étant plus considéré

  1. diviser :

  • on partage en 2 par la moitié le tableau trié

  1. régner :

    • on compare la valeur cherchée à la valeur médiane du tableau

    • si besoin, on en déduit la moitié gauche ou droite du tableau qui contient la valeur cherchée

    • on recommence la recherche sur la “bonne moitié”

4.3.2. Algorithme itératif#

Analyse

Il faut :

  1. itérer :

    • le test de la valeur de l’indice milieu

    • le découpage en 2 du tableau

  2. arrêter :

    • quand on a trouvé la valeur cherchée

    • ou si la taille du tableau est égale à zéro (tableau vide)

  3. retourner un booléen

Codage

  • L’appel s’effectue en indiquant :

    • la valeur cherchée

    • le tableau

    • sa taille

  • Le nombre d’itérations n’est a priori pas connu (il est borné en revanche) donc boucle while

  • L’indice milieu est obtenu avec une division entière // sachant que le milieu entre \(a\) et \(b\) est \((a+b)//2\)

    • Rappel : la division entière // retourne le quotient de la division euclidienne

  • D’une itération à l’autre :

    • choisir la partie gauche ou droite du tableau revient à changer l’indice de début et de fin du prochain tableau à traiter : on introduit des indices g, d et m pour désigner les indices de gauche, de droite et du milieu qui vont définir extrémités des parties droites et gauches du tableau. Ainsi : pour m = (g+d)//2,

      • t[g, m[ est la partie gauche du tableau et t[g, d[

      • t[m, d[ est la partie droite du tableau et t[g, d[

    • la taille est divisée par 2

Note

En cohérence avec les conventions de python, l’indice de l’extrémité droite du tableau n’est pas atteint.

def dichotomie_iterative(val: int, tab: list[int], dim: int) -> bool:
    '''recherche dichotomique : version itérative
    entrées - val :int cherché
            - t : tableau d'int de taille dim, trié par ordre croissant
    sortie : vrai si val est dans t, faux sinon           
    '''
    g = 0          # tab[g, d[
    d = dim        
    
    while g < d: # t[g, g[ est vide
        m = (g + d)//2   # indice milieu de t[g,d[
        if tab[m] == val:
            return True
        elif tab[m] > val: # val est dans la partie gauche : t[g,m[
            d = m
        else:              # val est dans la partie droite : t[m+1, d[
            g = m + 1
    return False

Note

Pour cette recherche par dichotomie, le tableau droit est en fait t[m+1, d[.

Warning

Ici aussi, l’ordre du traitement du test if/elil/else est important : l’accès tab[m] doit être “protégé” car il est susceptible de lever une exception (débordement de tableau).

v = 1
print(v, "dans ", t, "?", dichotomie_iterative(v, t, len(t)))
v = 3
print(v, "dans ", t, "?", dichotomie_iterative(v, t, len(t)))
v = 7
print(v, "dans ", t, "?", dichotomie_iterative(v, t, len(t)))

1 dans  [0, 1, 1, 2, 3, 4, 4, 5, 9, 10] ? True
3 dans  [0, 1, 1, 2, 3, 4, 4, 5, 9, 10] ? True
7 dans  [0, 1, 1, 2, 3, 4, 4, 5, 9, 10] ? False

Tests unitaires.

  • Le tableau t est trié. On peut donc reprendre les tests utilisés jusque-là.

  • De même, le tableau vide est trié. On peut y appliquer la recherche dichotomique.

# t = [0, 1, 1, 2, 3, 4, 4, 5, 9, 10]
assert dichotomie_iterative(1, t, len(t)) == True
assert dichotomie_iterative(3, t, len(t)) == True
assert dichotomie_iterative(7, t, len(t)) == False
# tableau vide
assert dichotomie_iterative(0, [], 0) == False

4.3.3. Algorithme récursif#

Analyse

  1. Récursion

    • il faut appeler récursivement la recherche sur le sous-tableau (gauche ou droite) qui va bien

  2. Terminaison : 2 cas

    • on a trouvé la valeur cherchée

    • le tableau est vide

Codage

Récursion : “le sous-tableau (gauche ou droite) qui va bien”

  • il faut pouvoir préciser les indices gauche et droit du sous-tableau traité

    • donc paramètres formels : g et d

  • et sa taille (parce qu’on manipule un tableau)

    • donc paramètre formel dim

Rmq.: Bien que la recherche ne s’effectue que sur la partie tab[g, d[ du tableau tab, le paramètre de taille dim reste égal à len(tab).

def dichotomie(val: int, t: list[int], dim: int, g: int, d: int) -> bool:
    '''recherche dichotomique : version récursive
    recherche val dans t[g, d[ et retourne True ou False
    entrées. val : int, t: tableau d'int de taille n,
    g, d : int indices gauche et droite
    '''
    if g >= d:       
        return False # t[g,g[ est vide
    m = (g + d) // 2 
    if t[m] == val:
        return True
    elif val < t[m]: # val est dans la partie gauche t[g, m[ 
        return dichotomie(val, t, dim, g, m)
    else:            # val est dans la partie droite t[m+1, d[ 
        return dichotomie(val, t, dim, m + 1, d)

        
def dichotomie_recursive(val: int, t: list[int], dim: int) -> bool:
    '''recherche dichotomique de val dans t de taille dim_t
    pour ressembler ) la version iterative en utilisant dichotomie
    '''
    return dichotomie(val, t, dim, 0, dim)

Warning

Pour les mêmes raisons que la version itérative, l’ordre du test est important pour éviter de lever une exception (débordement de tableau).

# t = [0, 1, 1, 2, 3, 4, 4, 5, 9, 10]
assert dichotomie_recursive(1, t, len(t)) == True
assert dichotomie_recursive(3, t, len(t)) == True
assert dichotomie_recursive(7, t, len(t)) == False
# tableau vide
assert dichotomie_recursive(0, [], 0) == False

Remarque

  • Observer et bien comprendre pourquoi le traitement récursif dichotomie comporte 4 return

    • Essayer par exemple de supprimer les 2 derniers

  • L’encapsulation de dichotomie dans dichotomie_recursive permet un appel de plus haut niveau similaire à la version itérative. Dans l’absolu, il n’est pas nécessaire : c’est l’appel principal de dichotomie qui résout le problème..

Exercices

  • Instrumenter le code (ajouter des print() :) pour exhiber l’évalution de g, d et m

  • Effectuer les 2 recherches précédentes sans utiliser dichotomie_recursive mais seulement dichotomie

4.4. Complexité des algorithmes de recherche#

Nous allons montrer que la recherche séquentielle est un algorithme de complexité linéaire tandis que la recherche dichotomique est de complexité logarithmique. Ce qui justifie l’intérêt l’approche dichotomique pour des tableaux triés de grande taille.

4.4.1. Les paramètres de l’analyse de la complexité#

Paramètre de complexité : le nombre de valeurs présentes, c-a-d. la taille dim du tableau de stockage.

Notons \(n\) ce paramètre et t ce tableau.

Mesure de la complexité : la comparaison t[i] == val dans le cas séquentiel itératif, ou t[g] == val dans le cas séquentiel récursif ou enfin t[m] == val dans le cas dichotomique.

On va donc chercher la quantité \(C(n)\) qui compte le nombre de ces comparaisons comme une fonction de la taille \(n\) du tableau de stockage.

4.4.2. Analyse de la recherche séquentielle itérative#

Le nombre de comparaisons dépend de la position de val dans t :

  • meilleur cas : val est présent à l’indice 0 : 1 comparaison suffit

  • pire cas : val est absent de t donc le parcours du tableau est complet (quelque soit l’écriture) et comporte \(n\) comparaisons

  • dans le cas général : traitement effectué avec un nombre de comparaisons inférieur ou égal à \(n\)

Donc \(1 \le C(n) \le n\).

La complexité en temps de la recherche séquentielle dans un tableau de \(n\) valeurs est au pire linéaire en \(n\).

Sa complexité asymptotique est telle que : \(C(n) = \cal{O}(n)\).

4.4.3. Analyse de la recherche dichotomique, version itérative#

La dichotomie effectue des divisions successives de la taille du tableau dans laquelle la recherche est effectuée. Il est commode de commencer l’analyse avec \(n = 2^p\) pour obtenir des tailles successives entières.

Remarquons dès maintenant :

  • si \(n = 2^p\) alors \(p = \log_2(n)\)

  • si \(2^p \le n < 2^{p+1}\) alors \(p =\) int(\(\log_2(n)\)).

Cette dernière ligne explicite l’intérêt de commencer avec \(n = 2^p\).

Principe de l’analyse.

Le nombre de comparaisons dépend de la position de val dans t :

Meilleur cas : val est présent à l’indice m == n//2 et 1 comparaison suffit

Pire cas : val est absent de t

  • la recherche s’effectue successivement sur des tableaux de taille \(n, n/2, n/4, \dots, 4, 2, 1\) jusqu’à terminaison avec g == d, c-a-d. un tableau vide, soit donc \(p = \log_2(n)\) divisions par 2 avant terminaison

  • pour chacune de ces tailles, une comparaison t[m] == val est effectuée

Donc \(C(n) = p = \log_2(n)\) dans le pire des cas pour \(n = 2^p\).

Et pour le pire cas d’une taille \(n\) quelconque, int\((\log_2(n)) \le C(n) <\) int\((\log_2(n))+1\).

La complexité en temps de la recherche séquentielle dans un tableau de \(n\) valeurs est au pire majorée par le logarithme de \(n\).

Sa complexité asymptotique est telle que : \(C(n) = \cal{O}(\log(n))\).

Rmq. Les valeurs successives de la taille des tableaux traités sont celles de la suite géométrique de raison \(1/2\) et de premier terme \(n\). Une telle suite converge vers 0. Ce qui permettra de prouver la terminaison de l’algorithme.

Exercice.

La complexité logarithmique de la recherche dichotomique en version itérative peut aussi se démontrer en prouvant (par récurrence) que la taille de l’intervalle après \(k\) itération de \([g, d[\), \(|d - g| < n / 2^k\).

4.4.4. Analyse de la recherche dichotomique, version récursive#

On retrouve facilement la complexité logarithmique de la recherche dichotomique dans sa version récursive.

On simplifie l’analyse en observant un pire cas et \(n = 2^p\).

Soit \(C(n)\) le nombre de comparaisons effectuées par la recherche dichotomique dans \(n\) valeurs.

Une étape de récursion de cette recherche :

  • effectue une comparaison : t[m] == val

  • “appelle” la récursion pour \(n/2\).

La terminaison est obtenue dans le pire cas pour \(C(1) = 1\) (ou \(C(0) = 0\)).

Soit donc directement : $\(C(n) = 1 + C(n/2)\)\( et \)\(C(1) = 1.\)$

On développe cette relation de récurrence pour \(n, n/2, ..., 1\).

Ce qui donne : \(C(n) = 1 + 1 + \dots + 1 = \log_2(n)\).

On remarque que l’analyse de la version récursive conduit naturellement à une relation de récurrence.

Exercice.

De façon similaire, retrouver la complexité linéaire de la recherche séquentielle en version récursive.

4.5. (\(\star\)) Preuves de terminaison et de correction#

Nous illustrons comment prouver :

  • qu’un algorithme termine

  • qu’un algorithme est correct, c-a-d. qu’il termine en trouvant bien la solution du problème.

4.5.1. Terminaison de la recherche séquentielle : version itérative#

Il s’agit de montrer que l’exécution de l’algorithme termine son exécution quelques soient les entrées de l’instance. Dans un premier temps, on ne s’intéresse pas à la validité de la solution ainsi trouvée.

Dans le cas d’un algorithme itératif, une technique classique pour prouver la terminaison de l’algorithme est d’identifier un variant de boucle ou variant de l’itération.

Variant de boucle : une quantité entière et positive qui décroît strictement à chaque itération de la boucle.

La terminaison de l’algorithme itératif est prouvé si ce variant arrête la répétition (la boucle) – et ce quelques soient les entrées de la répétition.

Reprenons une version itérative de la recherche séquentielle.

Celle avec le while est la plus simple pour commencer.

def rech_seq_while(val: int, tab: list[int], dim: int) -> bool:
    i = 0
    while i < dim:
        if tab[i] == val:
            return True
        i = i + 1 
    return False

Exemple de preuve de terminaison

Aucune quantité de l’algo ainsi écrit est explicitement un variant.

Cependant la condition d’arrêt i < dim permet de ré-écrire une variable d’itération j = dim - i que l’on va prouver être un variant de la boucle.

  • avant la première itération boucle : l’entier j == dim qui est positif si le tableau t n’est pas vide

  • chaque itération de la boucle décrémente j de 1 (car elle incrémente i de 1)

  • j est donc un entier, positif qui décroît par pas de 1 à partir de dim,

  • donc, à terme (i.e. à un certain moment), j vaut 0.

    • mathématiquement les valeurs de j suivent une suite arithmétique de raison -1 et de premier terme dim > 0.

  • Quand j == 0, i == dim, valeur qui ne vérifie pas la condition de test de la ligne 5 et qui arrête donc la répétition.

On a bien identifié un variant qui prouve la terminaison de cette recherche séquentielle (version itérative while).

Rmq.

  • Ceci est aussi vrai pour un tableau vide : dim == 0.

  • Ce qui permet d’écrire une solution valide avec tout tableau même vide, sans traitement spécifique de ce cas.

Ainsi, on écrit l’algorithme avec une répétition while contrôlée par ce variant j : c-a-d. en prenant j comme indice, initialisé à dim et la condition d’arrêt j > 0. Cette ré-écriture est un changement de variable “classique”.

def rech_seq_while_variant(val: int, tab: list[int], dim: int) -> bool:
    '''recherche équentielle itérative : s'il fallait n'en garder qu'une !'''
    assert dim == len(tab)

    j = dim
    while j > 0:
        if tab[j - 1] == val:
            return True
        j = j - 1 
    return False

#  t = [0, 1, 1, 5, 2, 10, 4, 4, 9, 3]
assert rech_seq_while_variant(1, t, len(t)) == True
assert rech_seq_while_variant(3, t, len(t)) == True
assert rech_seq_while_variant(7, t, len(t)) == False
# tableau vide
assert rech_seq_while_variant(0, [], 0) == False

Exercice

  • Adapter cette preuve de terminaison à la version avec une boucle for.

4.5.2. Correction de la recherche séquentielle : version itérative#

Il s’agit maintenant de prouver que l’algorithme (qui termine) calcule la solution attendue – et ce quelques soient les instances de problèmes concernées.

La preuve de la correction d’un algorithme itératif repose souvent sur la notion d’invariant de boucle.

Un invariant de boucle est une propriété vérifiée tout au long de l’exécution d’une boucle et qui exhibe la correction de l’algorithme à la terminaison de la boucle.

La preuve s’effectue en 3 étapes. En notant (P) cette propriété :

  1. initialisation : (P) est vraie avant la première itération du corps de la boucle

  2. conservation : On suppose (P) vraie avant la i-ème itération. On montre que la i-ème itération conserve (P). C-a-d. que (P) vraie avant la i-ème itération reste vraie avant la (i+1)-ème itération.

  3. terminaison : (P) est vraie après la dernière itération.

En pratique :

  • la propriété appliquée à la sortie de boucle (terminaison) prouve que celle-ci a effectué le traitement prévu

    • exemple : la recherche séquentielle étant “réduite” à une boucle, son invariant prouvera que la solution retournée par le traitement est exacte : soit True si la valeur est présente dans t et False sinon.

  • l’initialisation, c-a-d. avant la boucle, prouve que les variables sont correctement initialisées

  • la conservation et la terminaison prouvent que l’indice de boucle et le nombre d’itérations sont corrects.

  • initialisation et conservation constituent une preuve par récurrence “classique”

Prouvons que la propriété suivante :

(P) Avant l’itération i, si val est présent dans t, il est présent dans t[i, dim-1]

est un invariant de la boucle de la recherche séquentielle :

    i = 0
    while i < dim:
        if t[i] == val:
            return True
        i = i + 1 
    return False

La contraposée de (P) est :

(P) Avant l’itération i, si val est absent de t[i, dim-1], il est absent de t.

1. Initialisation. Avant la première itération, i==0 et t[0,dim-1] est le tableau tout entier. Donc (P) est trivialement vraie.

2. Conservation. D’après (P), avant la i-ième itération pour val présent dans t, val est dans t[i, dim-1]. Donc val == t[i] ou val = t[j] pour i+1 <= j < dim.

  • si i < dim, l’itération s’effectue et t[i] est valide.

    • si t[i] != val, val est donc dans t[i+1, dim-1] d’après (P). i est incrémenté donc (P) est bien conservée après l’itération i.

    • si t[i] == val, val est bien dans t[i, dim-1]. i n’est pas modifié, l’itération s’arrête et (P) reste vrai.

3. Terminaison. 2 cas.

  • Si i==dim alors la conservation de (P) à l’itération précédente dit que si val est présent dans t, il est présent dans t[dim, dim-1], ce qui est impossible car t[dim, dim-1] est vide. Donc val est absent dans t selon la contraposée de (P).

  • Sinon (cas déjà vu), val est présent en position i dans t (et est bien dans t[i, dim-1]).

Rmq.

  • L’identification de l’invariant est plus difficile que sa preuve.

  • L’invariant est une propriété caractéristique de l’algorithme itératif.

    • Dit simplement, l’invariant formalise “ce qui fait marcher” l’algorithme.

    • Il n’y a pas qu’un seul invariant possible, bien sûr.

4.5.3. Terminaison de la recherche dichotomique#

Lors de l’analyse de complexité de la recherche dichotomique, on a indiqué pour le pire cas :

  • que la condition d’arrêt g >= d commune aux formulations itérative et récursive correspond à un tableau vide, i.e. de taille 0,

  • que la taille d - g des tableaux successifs de la dichotomie suivaient la suite géométrique de raison \(1/2\) et de premier terme \(n\).

Cette suite de termes positifs converge vers 0. Ce qui prouve la terminaison de l’algorithme par vérification de la condition d’arrêt :

  • de façon explicite dans le cas récursif

  • en considérant d-g (entier positif) comme variant dans le cas itératif.

4.5.4. (\(\star\star\)) Correction de la recherche dichotomique : version itérative#

Prouvons que la propriété suivante est un invariant de la boucle de la recherche dichotomique.

Invariant (P) :

si val est présent dans t alors il est dans t[g,d].

Avant de prouver (P), énonçons sa contraposée :

si val n’est pas dans t[g,d] alors val n’est pas présent dans t.

Par commodité, on rappelle l’algorithme concerné (sans la spécification de la fonction). Il est légèrement différnet de celui présenté plus haut : il travaille avec un tableau t[g, d].

    g = 0          # indice de gauche du tableau exploré
    d = dim_t - 1  # indice de droite du tableau exploré    
    while g <= d:
        m = (g + d)//2   # indice milieu de t[g,d]
        if t[m] == val:
            return True
        elif t[m] > val: # val est dans la partie gauche : t[g,m-1]
            d = m - 1
        else:            # val est dans la partie droite : t[m+1,d]
            g = m + 1
    return False

Dans l’énoncé de (P), “est présent” correspond à la valeur renvoyée True, et inversement pour la contraposée.

Sans perdre de généralité, on facilite l’écriture de la preuve en supposant que toutes les valeurs de t sont différentes (ce qui donne des inégalités strictes) et on note n = dim_t.

Appelons pivot la valeur de t[m] où m = (g+d)//2.
Chaque itération effectuée teste donc si la valeur du pivot est celle cherchée, et sinon continue le traitement sur une des deux parties à droite ou à gauche du pivot (d’où son nom).

La preuve de l’invariant repose sur la propriété simple suivante :

  • les valeurs “à gauche” du pivot sont inférieures au pivot,

  • et inversement pour celles “à droite” du pivot.

Ce qui ce formalise comme suit :

  • t[i] < pivot pour g <= i < m

  • t[i] > pivot pour m < i <= d

Preuve de (P).

Globalement, l’algorithme met à jour g ou d jusqu’à avoir trouvé val ou … être sûr de ne plus pouvoir le trouver. Ces 4 aspects sont les clés de la preuve de :

(P) si val est présent dans t alors il est dans t[g,d].

1. Initialisation

  • Avant la première itération, g==0 et d==n-1donc t[g,d] == t[0,n-1], c-a-d. le tableau t (en entier). Donc (P) est (trivialement) vraie.

2. Conservation Au début d’une itération donnée, (P) assure que si val est présent, il existe j tel que t[j]==val avec g <= j <= d.

  • si j == (g+d)//2 == m alors ni g ni d sont modifiés par l’itération et (P) reste donc vraie au début de l’itération suivante avec g <= m <= d.

  • si val < pivot (== t[m]) alors d=m-1. Montrons que val présent est dans t[g, m-1]. On sait que t[i] < pivot pour g <= i < m et t[i] > pivot sinon. Donc val < pivot présent est bien dans t[g,m-1]==t[g,d] et non dans le reste de t. (P) reste vraie au début de l’itération suivante.

  • si val > pivot (== t[m]) alors g=m+1 et cette fois val est présent dans t[m+1,d]. En effet, t[i] > pivot pour m < i <= d et t[i] < pivot sinon. Donc val > pivot est présent dans t[m+1,d] == t[g,d] et non dans le reste de t. (P) reste aussi vraie au début de l’itération suivante.

3. Terminaison: La boucle while se termine dans 2 cas.

  • cas a : on a trouvé m dans tel que val == t[m] sans modifier g et d depuis l’itération précédente. Donc val est présent en t[m] avec g <= m <= d donc (P) est vrai pour t[g,d] après la dernière itération.

  • cas b : si g > d, t[g,d] est vide donc val n’est pas dans t[g,d]. La conservation de la contraposée de (P) prouve que val n’est pas présente dans t après la dernière itération. Ce qui prouve (P) dans ce cas de terminaison aussi.

Conclusion. Les 2 cas de la terminaison prouvent la correction de l’algorithme étudié.

Rmq.

  • Dans la preuve précédente, la validité de (tous les) t[g,d] est implicite : aucun indice ne se trouve à l’extérieur du tableau t[0, dim_t]. Si besoin, on peut compléter chaque encadrement avec 0 <= g et d < dim_t, se convaincre que 0 <= g <= m <= d < dim_t et compléter la formulation de l’invariant comme suit :

(P) si val est présent dans t alors il est dans t[g,d] avec 0 <= g et d < dim_t.

4.6. Synthèse#

  • Deux algorithmes simples de recherche : séquentielle et dichotomique sur tableau trié

    • complexité linéaire vs. logarithmique

    • meilleurs cas, pire cas

  • Exemples d’écritures itératives ou récursives du même algorithme

    • en-têtes identiques par encapsulation de l’appel récursif principal

  • Exemples d’analyse de complexité

  • (\(\star\)) Exemples de preuve de terminaison et de correction

    • algo itératif : variant et invariant de boucle

Contents