Partie 1 : Parcours séquentiel et recherche dichotomique

B.O. spécial n° 1 du 22 janvier 2019 - NSI Première

Contenus	Capacités attendues	Commentaires
Parcours séquentiel d'un tableau.	Écrire un algorithme de recherche d'une occurrence ou d'un extremum.	On écrira des algorithmes de recherche d'un élément, de recherche d'un extremum.
Recherche dichotomique dans un tableau trié.	Montrer la terminaison de la recherche dichotomique à l'aide d'un variant de boucle.	Des tests de comparaison d'efficacité seront menés.

1. Parcours séquentiel

1.1 Principe

Le parcours séquentiel (ou recherche linéaire) consiste à examiner les éléments d'un tableau un par un, du premier au dernier, jusqu'à trouver ce que l'on cherche ou atteindre la fin du tableau.

C'est l'algorithme le plus simple et le plus naturel. Il fonctionne sur n'importe quel tableau, trié ou non.

1.2 Recherche d'une occurrence

On cherche si un élément valeur est présent dans un tableau tab. Si oui, on renvoie son indice ; sinon, on renvoie -1.

def recherche(tab, valeur):
    """Renvoie l'indice de la première occurrence de valeur, ou -1."""
    for i in range(len(tab)):
        if tab[i] == valeur:
            return i
    return -1

>>> recherche([3, 7, 2, 9, 5], 9)
3
>>> recherche([3, 7, 2, 9, 5], 6)
-1

1.3 Recherche du maximum

def indice_maximum(tab):
    """Renvoie l'indice du maximum d'un tableau non vide."""
    assert len(tab) > 0, "Le tableau ne doit pas être vide"
    i_max = 0
    for i in range(1, len(tab)):
        if tab[i] > tab[i_max]:
            i_max = i
    return i_max

>>> indice_maximum([3, 7, 2, 9, 5])
3
>>> indice_maximum([10])
0

1.4 Compter les occurrences

def compter(tab, valeur):
    """Renvoie le nombre d'occurrences de valeur dans tab."""
    compteur = 0
    for element in tab:
        if element == valeur:
            compteur += 1
    return compteur

1.5 Calculer une moyenne

def moyenne(tab):
    """Renvoie la moyenne des éléments du tableau."""
    assert len(tab) > 0, "Le tableau ne doit pas être vide"
    somme = 0
    for element in tab:
        somme += element
    return somme / len(tab)

1.6 Coût du parcours séquentiel

Situation	Nombre de comparaisons
Meilleur cas (élément en première position)	1
Pire cas (élément absent ou en dernière position)	n
Cas moyen	n / 2

Le parcours séquentiel a une complexité en O(n) : le temps d'exécution est proportionnel à la taille du tableau.

2. Recherche dichotomique

2.1 Principe

La recherche dichotomique (du grec dikho, « en deux ») ne fonctionne que sur un tableau trié. À chaque étape, on divise l'intervalle de recherche en deux en comparant la valeur cherchée à l'élément du milieu.

C'est le principe du jeu « plus grand, plus petit ».

2.2 Déroulement d'un exemple

Cherchons la valeur 23 dans le tableau trié [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] :

Étape	gauche	droite	milieu	tab[milieu]	Action
1	0	9	4	16	23 > 16 → chercher à droite
2	5	9	7	56	23 < 56 → chercher à gauche
3	5	6	5	23	23 == 23 → trouvé !

En 3 étapes au lieu de 6 avec un parcours séquentiel.

2.3 Implémentation

def recherche_dichotomique(tab, valeur):
    """Recherche valeur dans tab (trié) par dichotomie.
    Renvoie l'indice si trouvé, -1 sinon.
    Precondition: tab est trié en ordre croissant.
    """
    gauche = 0
    droite = len(tab) - 1

    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tab[milieu] == valeur:
            return milieu
        elif tab[milieu] < valeur:
            gauche = milieu + 1
        else:
            droite = milieu - 1

    return -1

>>> tab = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
>>> recherche_dichotomique(tab, 23)
5
>>> recherche_dichotomique(tab, 20)
-1

2.4 Terminaison

Pour prouver que l'algorithme se termine (ne boucle pas indéfiniment), on utilise un variant de boucle : une quantité entière qui :

Est positive ou nulle à chaque itération
Diminue strictement à chaque itération

Ici, le variant est droite - gauche :

Initialement, droite - gauche = n - 1 (positif)
À chaque itération, soit gauche augmente, soit droite diminue → le variant diminue
Quand droite - gauche < 0, la condition gauche <= droite est fausse et la boucle s'arrête

2.5 Correction

Pour prouver que l'algorithme est correct (donne le bon résultat), on utilise un invariant de boucle : une propriété vraie à chaque itération.

Invariant : « Si valeur est dans tab, alors elle se trouve à un indice compris entre gauche et droite. »

Initialisation : vrai car gauche = 0 et droite = len(tab) - 1 couvrent tout le tableau
Conservation : si tab[milieu] < valeur, la valeur est forcément à droite de milieu (car le tableau est trié), donc gauche = milieu + 1 préserve l'invariant
Terminaison : quand gauche > droite, l'intervalle est vide, donc la valeur n'est pas dans le tableau

2.6 Complexité

À chaque étape, l'intervalle de recherche est divisé par 2.

Pour un tableau de n éléments, le nombre maximal d'étapes est $\lceil \log_2(n) \rceil + 1$ :

Taille du tableau	Parcours séquentiel (pire cas)	Dichotomie (pire cas)
10	10	4
100	100	7
1 000	1 000	10
1 000 000	1 000 000	20
1 000 000 000	1 000 000 000	30

La recherche dichotomique a une complexité en O(log₂ n), incomparablement plus rapide que le parcours séquentiel en O(n).

À retenir

Le parcours séquentiel examine les éléments un par un. Complexité : O(n).
Il permet de chercher une valeur, un extremum, de compter, de calculer une somme ou une moyenne.
La recherche dichotomique divise l'intervalle de recherche en deux à chaque étape. Complexité : O(log₂ n).
Elle nécessite un tableau trié.
On prouve la terminaison avec un variant de boucle (quantité qui décroît strictement).
On prouve la correction avec un invariant de boucle (propriété toujours vraie).