Recherche séquentielle, dichotomique, arrière

Chercher une valeur est sans doute l'opération la plus fréquente d'un programme. Ce chapitre présente trois façons de parcourir l'espace de recherche : du début vers la fin (séquentielle), en coupant l'espace en deux à chaque étape (dichotomique), de la fin vers le début (arrière). Chaque programme est écrit à partir d'une propriété invariante, selon la méthode du chapitre 11 : initialisation, progression, arrêt.

12.1 Recherche séquentielle

On parcourt le tableau de gauche à droite. À tout instant, on a examiné les cases d'un préfixe $T[0:i]$ sans y trouver $x$. C'est l'invariant :

$$I(i):x\notin T[0:i].$$

• Initialisation. $I(0)$ est vraie : le préfixe $T[0:0]$ est vide.
• Progression. $I(i)$ et $i\ne n$ et $T[i]\ne x$ $\Rightarrow$ $I(i+1)$.
• Arrêt. Lorsque $i=n$, on a $x\notin T[0:n]$ : $x$ est absent. Lorsque $T[i]=x$, $i$ est le premier indice cherché, puisque $x\notin T[0:i]$.

static int rechercheSeq(int[] T, int x) { int n = T.length;
    int i = 0;
    // I(i) : x n'est pas dans T[0:i]
    while (i < n && T[i] != x)
        i = i + 1;       // I(i) et T[i] != x ==> I(i+1)
    // I(i) et (i == n ou T[i] == x)
    if (i == n) return -1; // x n'est pas dans T[0:n]
    return i;              // T[i] == x et x n'est pas dans T[0:i]
}

Complexité.

Le corps de boucle est en temps constant ; il est exécuté au plus $n$ fois. Dans le pire cas ($x$ absent, ou présent seulement en dernière case), le temps de calcul est de la forme $\alpha n+\beta$ : la recherche séquentielle est en $\Theta (n)$. On ne peut pas faire mieux sur un tableau quelconque : tant qu'une case n'a pas été lue, elle pourrait contenir $x$.

12.2 Recherche dichotomique

Si le tableau est trié, chaque case lue renseigne aussi sur ses voisines. Comparer $x$ à la case du milieu permet d'éliminer d'un seul coup la moitié du tableau : c'est la dichotomie (du grec : « couper en deux »). C'est ainsi que l'on cherche un mot dans un dictionnaire papier.

12.2.1 Le bon problème : la position d'insertion

Plutôt que « $x$ est-il dans $T$ ? », on résout un problème un peu plus général, qui a toujours une réponse et qui se programme sans cas particulier.

Par exemple avec $S=[1,3,3,3,6,8,11,15]$ : la position d'insertion de $3$ est $1$ (la première occurrence de $3$), celle de $7$ est $5$, celle de $0$ est $0$, celle de $20$ est $8=n$. Une fois $i$ connu, $x$ est dans $T$ si et seulement si $i<n$ et $T[i]=x$.

12.2.2 L'invariant

On maintient deux indices $g$ et $d$ qui délimitent la zone d'incertitude $[g:d]$ : à gauche de $g$ tout est $<x$, à partir de $d$ tout est $\ge x$.

$$I(g,d):T[0:g]<x\text{et}T[d:n]\ge x.$$

• Initialisation. $g=0$ et $d=n$ : les deux sous-tableaux $T[0:0]$ et $T[n:n]$ sont vides, $I(0,n)$ est vraie.
• Arrêt. Lorsque $g=d$, la zone d'incertitude est vide : $T[0:g]<x\le T[g:n]$ ; $g$ est la position d'insertion.
• Progression. Si $g<d$, soit $m$ un indice de $[g:d]$ (au milieu). Comme $T$ est trié :

• si $T[m]<x$, alors $T[0:m+1]<x$ : $I(m+1,d)$ est vraie ;
• sinon $T[m]\ge x$, donc $T[m:n]\ge x$ : $I(g,m)$ est vraie.

Dans les deux cas, la zone d'incertitude a strictement diminué, car $g\le m<d$.

static int premierIndice(int[] T, int x) { int n = T.length;
    int g = 0, d = n;
    // I(g,d) : T[0:g] < x  et  T[d:n] >= x
    while (g < d) {
        int m = g + (d - g) / 2;      // g <= m < d
        if (T[m] < x) g = m + 1;      // T[0:m+1] < x  ==> I(m+1,d)
        else d = m;                   // T[m:n] >= x   ==> I(g,m)
    }
    // I(g,d) et g == d : T[0:g] < x et T[g:n] >= x
    return g;
}

static boolean dans(int[] T, int x) { // T trié croissant
    int i = premierIndice(T, x);
    return i < T.length && T[i] == x;
}