Recherche dichotomique dans un tableau

I. Introduction

Tout le monde a déjà joué au jeu « trouve un nombre entier entre 1 et 100 » : on commence par proposer le nombre du milieu, soit 50. Si la réponse est « c'est plus », on propose de nouveau celui du milieu, soit 75, et ainsi de suite jusqu'à trouver le nombre cherché. C'est ce qu'on appelle une recherche dichotomique.

Des volumes importants de données sont susceptibles d'être traités par les ordinateurs. Des algorithmes efficaces sont alors nécessaires pour réaliser des opérations comme la sélection et la récupération de données. Les algorithmes de recherche entrent dans cette catégorie : leur rôle est de déterminer si une donnée est présente et, le cas échéant, d'en indiquer la position. La recherche d'une information dans un annuaire illustre cette idée.

La recherche dichotomique permet de traiter efficacement les données d'un tableau trié. L'idée centrale repose sur la réduction de moitié de l'espace de recherche à chaque étape : on regarde la valeur du milieu et si ce n'est pas celle recherchée, on sait si l'on doit continuer dans la première ou dans la seconde moitié. En répétant ce principe, on divise par 2 à chaque fois la zone de recherche et l'on arrive très rapidement soit à la valeur cherchée, soit à un intervalle vide.

Ce principe est connu sous le nom de « diviser pour régner » (divide and conquer). La recherche dichotomique en est l'exemple le plus simple. Cet algorithme est aussi utilisé en mathématiques pour déterminer une valeur approchée des solutions d'une équation $f(x) = k$.

En terminale, nous verrons que ce type d'algorithme est en général implémenté de manière récursive, mais la récursivité n'est pas au programme de 1re.

II. Recherche séquentielle dans un tableau

1. Recherche « naïve »

Une première façon de rechercher une valeur dans un tableau est d'effectuer une recherche « naïve » : parcourir toutes les valeurs jusqu'à trouver ce que l'on cherche.

En pseudo-langage, la fonction ci-dessous retourne l'indice de la valeur cherchée si elle est dans le tableau et −1 sinon :

fonction recherche_naive(T, val) {   # T : tableau d'indices 0 à n-1 ; val : valeur cherchée
    Pour i allant de 0 à n - 1 :
        Si val == T[i] {                 # la valeur est dans le tableau
            retourner i
        }
    retourner -1                     # la valeur n'est pas dans le tableau
}

Il est évident que l'algorithme termine (boucle for bornée) et donne le résultat attendu.

La complexité en temps de cet algorithme est linéaire : dans le pire des cas, il faut parcourir les $n$ valeurs du tableau. Le temps de recherche double quand la longueur de la liste double. Le fait que le tableau soit trié ne change rien à cette complexité.

2. Recherche par dichotomie dans un tableau trié

Le mot dichotomie vient du grec dikhotomia signifiant « diviser en deux parties égales ». L'idée principale est de réduire de moitié l'espace de recherche à chaque étape.

En tenant compte du caractère trié (par ordre croissant) du tableau, on améliore la recherche en suivant la méthode :

1. On détermine l'élément m au milieu du tableau ;
2. si c'est la valeur recherchée, on s'arrête ;
3. sinon, deux cas sont possibles :
   • (a) si $m$ est strictement supérieur à la valeur recherchée, comme le tableau est trié par ordre croissant, la valeur cherchée ne peut se trouver que dans la première moitié (indices plus petits) ;
   • (b) sinon ($m$ est strictement inférieur à la valeur cherchée), il faut chercher dans la seconde moitié du tableau (indices plus grands).
4. On répète le procédé jusqu'à avoir trouvé la valeur recherchée, ou bien avoir réduit l'intervalle de recherche à un intervalle vide, indiquant que la valeur n'est pas présente.

Exemple « à la main » :

Ce qui se traduit en pseudo-code :

fonction dichotomie(T, val) {     # T : tableau trié d'indices 0 à n-1
    debut <- 0
    fin   <- n - 1
    tant que debut <= fin {
        milieu <- partie_entière((debut + fin) / 2)
        si T[milieu] == val {
            renvoyer milieu }          # la valeur est trouvée
        sinon si T[milieu] > val {
            fin <- milieu - 1 }       # chercher dans la moitié gauche
        sinon {
            debut <- milieu + 1 }    # chercher dans la moitié droite
    }
    renvoyer -1                   # la valeur n'est pas dans le tableau
}

III. Analyse de l'algorithme de dichotomie

a. Terminaison

La fonction dichotomie contient une boucle tant que. Pour prouver la terminaison, nous allons chercher un variant de boucle.

• La condition de boucle étant debut ≤ fin, la variable fin − debut reste positive ou nulle tant que la boucle tourne.
• Montrons que longueur décroît strictement à chaque itération. On définit milieu = (debut + fin) // 2, d'où debut ≤ milieu ≤ fin. Trois cas :
  • Si T[milieu] == val → on sort de la boucle via return, la terminaison est assurée.
  • Si T[milieu] > val → on pose fin₂ = milieu − 1. Alors fin₂ < milieu ≤ fin, donc fin₂ − debut < fin − debut : longueur décroît strictement.
  • Si T[milieu] < val → on pose debut₂ = milieu + 1. Alors debut ≤ milieu < debut₂, d'où fin − debut₂ < fin − debut : longueur décroît strictement.
• Lorsque longueur = fin − debut < 0, on a fin < debut, ce qui est exactement la condition d'arrêt de la boucle.

b. Correction

Deux cas sont à considérer selon que la valeur cherchée se trouve ou non dans le tableau.

Le cas où l'algorithme renvoie un indice positif ou nul est direct : l'instruction return milieu n'est exécutée que si T[milieu] == val, donc le résultat est correct.

Intéressons-nous au cas où l'algorithme renvoie −1, affirmant que la valeur est absente sans avoir examiné toutes les valeurs. Nous le prouvons par un invariant de boucle.

Initialisation : Avant la 1re boucle, debut = 0 et fin = n − 1 : si val est dans T, son indice est forcément entre 0 et n−1, donc (P) est vérifiée.

Hérédité : On suppose (P) vraie en entrée de boucle et on montre qu'elle l'est encore en sortie. Après avoir défini milieu, trois cas :

1. T[milieu] == val → on sort via return milieu, la valeur est trouvée, ce cas ne concerne pas la preuve d'invariant.
2. T[milieu] > val → comme le tableau est trié par ordre croissant, toutes les valeurs d'indice ≥ milieu sont supérieures ou égales à T[milieu], donc strictement supérieures à val. Ainsi, val ne peut se trouver qu'à un indice strictement inférieur à milieu, c'est-à-dire entre debut et milieu − 1. Après l'affectation fin ← milieu − 1, (P) est toujours vérifiée. ✓
3. T[milieu] < val → de même, les valeurs d'indice ≤ milieu sont inférieures à val, donc val ne peut se trouver qu'entre milieu + 1 et fin. Après debut ← milieu + 1, (P) est toujours vérifiée. ✓

c. Complexité de l'algorithme

Sur un exemple : Pour un tableau de 128 valeurs, la dichotomie réduit successivement la zone de recherche :

$128 \to 64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$

Au plus 7 itérations, contre jusqu'à 128 pour la recherche naïve. De plus, si l'on passe de 128 à 256 valeurs, la recherche naïve double le nombre d'itérations, alors que la dichotomie n'en ajoute qu'une seule.

Cas général : À chaque itération, la longueur du tableau est divisée par 2. On cherche le nombre $k$ de divisions nécessaires pour atteindre 1 à partir de $n$ :

La complexité de la recherche dichotomique est logarithmique, c'est-à-dire d'ordre $O(\log_2(n))$.

On constate que la fonction $\log_2$ croît bien plus lentement que la fonction linéaire $g(x) = x$, et que l'écart s'accentue quand $x$ augmente. L'algorithme de recherche dichotomique est donc bien plus efficace que la recherche naïve.

def devine_nombre(choix):
    """L'ordinateur doit deviner un nombre compris entre 1 et 1000
    choisi par l'utilisateur, le plus rapidement possible.

    choix : entier compris entre 1 et 1000
    renvoie le nombre de coups nécessaires (entier)"""