L'algorithme de recherche binaire

La recherche binaire (binary search) fait partie des algorithmes fondamentaux de l'informatique que tout bon informaticien se doit de connaître. Dans leur célèbre livre A Method Of Programming, Edsger W. Dijkstra et W.H.J. Feijen qualifient même cet algorithme de «quasi canonique»:

The binary search [...] is an important, almost canonical, algorithm. It should be familiar in all its details to any educated computer scientist.

Je constate cependant que rares sont les programmeurs qui aujourd'hui, sont capables de comprendre et d'implémenter correctement cet algorithme. Ils l'ont peut-être oublié, ou peut-être ne l'ont-ils jamais vraiment appris.

Le but de cet article est d'expliquer cet algorithme à l'aide de prédicats logiques et de vous permettre de l'implémenter de manière efficiente et correcte.

L'algorithme de recherche binaire permet de trouver efficacement un élément dans un tableau trié. Commençons par définir formellement ce qu'est la recherche d'un élément dans un tableau:

Si $a$ un tableau de taille $N$ , avec des index $0 \leq i < N$ et si $x$ est un élément de ce tableau, trouver $x$ dans $a$ revient à trouver l'index $i_x$ tel que $a[i_x]$ soit égal à $x$ .

$$i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x$$

Nous avons aussi dit que le tableau est trié (du plus petit au plus grand). Ca signifie que pour tout $i$ et $j$ , si $i$ est plus petit ou égal à $j$ alors $a[i]$ est aussi plus petit ou égal à $a[j]$ .

$$\forall i,j : 0 \leq i \leq j < N : a[i] \leq a[j]$$

Nous pouvons généraliser l'objectif de la recherche dans le cas où l'élément recherché $x$ est présent plusieurs fois. Dans ce cas, nous aimerions avoir l'index du premier $x$ . Autrement dit, l'élément qui précède $x$ doit être strictement plus petit que $x$ :

$$i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x \wedge a[i_x-1] < x$$

Cette nouvelle condition peut s'avérer problématique si $x$ est le tout premier élément du tableau $a$ . Dans ce cas, $i_x-1$ est égal à $-1$ et $a[-1]$ n'est pas défini. Nous pouvons résoudre ce problème en définissant un élément virtuel à la position $-1$ qui soit plus petit que tous les autres éléments du tableau:

$$a[-1] = - \infty$$

Nous sommes partis du principe que $x$ soit présent dans $a$ , mais nous pouvons lever cette contrainte en spécifiant que si $x$ n'est pas dans $a$ , alors on aimerait avoir l'index où il devrait être. Si $x$ est strictement plus petit que $a[0]$ , alors le prédicat est satisfait en mettant $i_x$ égal à $0$ . Si $x$ est strictement plus grand que $a[N-1]$ , l'index où il devrait être c'est $N$ , mais $a[N]$ n'est pas défini.Nous contournons le problème de la même manière que pour $a[-1]$ en définissant un nouvel élément virtuel à la position $N$ qui soit plus grand que tous les autres éléments du tableau:

$$a[N] = + \infty$$

On peut récrire le prédicat de la recherche ainsi:

$$i_x : 0 \leq x_i \leq N : a[i_x] \geq x \wedge a[i_x-1] < x$$

Au début, l'intervalle de recherche est $[0..N]$ , l'idée de l'algorithme de recherche binaire consiste à réduire cet intervalle à chaque itération afin de trouver $i_x$ . Nous définissons l'intervalle de recherche à l'aide de deux nouvelles variables : $L$ (pour left ou lower) et $R$ (pour right). Ces nouvelles variables devront en tout temps satisfaire l'invariant suivant:

$$L,R : 0 \leq L < R \leq N : a[L] < x \wedge a[R] \geq x$$

Pour commencer, nous pouvons initialiser $L$ à $-1$ et $R$ à $N$ . Grâce à nos deux éléments virtuels, l'invariant est satisfait, car $a[L] = - \infty < x$ et $a[R] = + \infty \geq x$ . Il nous suffit maintenant de réduire l'intervalle $]L,R]$ et quand $L$ sera juste à côté de $R$ , nous aurons $L = R-1$ et si l'invariant est toujours vrai, alors on aura $R : 0 \leq x_i \leq N : a[R] \geq x \wedge a[R-1] < x$ et $R$ sera le $i_x$ que nous cherchons.

Avant de coder la recherche binaire, il nous faut encore juste trouver comment réduire l'intervalle $]L,R]$ tout en conservant l'invariant. La solution consiste à prendre un $h$ n'importe où entre $L$ et $R$ ( $L < h < R$ ) et si $a[h]$ est strictement plus petit que $x$ , alors nous pouvons donner à $L$ la valeur de $h$ , car $a[L]$ serait strictement plus petit que $x$ comme nous ne modifions pas $R$ , l'invariant tiendrait toujours. Au contraire, si $a[h]$ est plus grand ou égal à $x$ , alors nous pouvons donner à $R$ la valeur de $h$ , car $a[R]$ serait plus grand ou égal à $x$ comme nous ne modifions pas $L$ , l'invariant tiendrait encore.

Tant que $L < R-1$ , on peut toujours trouver un $h$ entre $L$ et $R$ . On peut par exemple prendre $h = L+1$ ou $h = R-1$ , mais notre algorithme ne ferait que des tout petits pas vers la solution. Une manière plus efficace consiste à prendre $h$ au milieu de l'intervalle $]L,R]$ , autrement dit $h = \frac{L+R}{2}$ . $h$ est un index et doit être un nombre entier; nous devons alors arrondir $h$ vers un entier. On peut sans autre arrondir $h$ vers le haut ou vers le bas et nous décidons ici de l'arrondir vers le bas : $h = \lfloor\frac{L+R}{2}\rfloor$ . Si $L < R-1$ , alors $L < h = \lfloor\frac{L+R}{2}\rfloor < R$ . Si $L = R-1$ , la recherche est terminée et nous n'avons plus besoin de réduire l'intervalle.

Nous avons maintenant assez de logique et de math pour pouvoir écrire un algorithme de recherche binaire correct. Pour cet article, nous décidons de coder cet algorithme en Python:

def binary_search(a: list, x) -> int:
    L:int = -1
    R:int = len(a)
    while (L < R-1):
        h: int = (L+R) // 2
        if a[h] < x:
            L = h
        else:
            R = h
    return R

Python n'a pas de problème de dépassement de capacité (overflow) avec les entiers, mais la plupart des autres langages n'ont pas ce confort et l'opération L+R pourrait provoquer un dépassement de capacité. On pourrait alors sans autre remplacer h = (L+R) // 2 par h = L + (R-L) // 2 et ainsi supprimer le risque de dépassement de capacité.

Si on souhaite savoir si $x$ est présent dans $a$ et retourner un boolean, on peut alors écrire

def present(a: list, x) -> bool:
    R = binary_search(a, x)
    return R < len(a) and a[R] == x

Pour compléter, voici l'algorithme codé en C:

#include <stdbool.h>

int binary_search(int* a, int n, int x) {
    int L = -1;
    int R = n;
    while (L < R-1) {
        int h = L + (R-L) / 2;
        if (a[h] < x) {
            L = h;
        } else {
            R = h;
        }
    }
    return R;
}

bool present(int* a, int n, int x) {
    int R = binary_search(a, n, x);
    return (R < n && a[R] == x);
}

De nos jours, on écrit souvent des programmes ou des «apps» en utilisant des «frameworks» et en copiant des bouts de code trouvés sur Internet. Les programmeurs amateurs diront qu'il est inutile de comprendre les détails des algorithmes fondamentaux, car ils ont déjà été implémentés par des personnes très compétentes et qu'il suffit d'utiliser la bonne bibliothèque. L'informaticien qui se respecte ne peut se satisfaire d'une telle démarche et sa saine curiosité ne sera satisfaite que lorsqu'il aura compris et implémenté lui-même l'algorithme.

J'espère que cet article aura ravivé la mémoire de certains et éveillé chez d'autres l'envie d'étudier plus en détail la science et l'art de l'informatique. Voici pour conclure quelques livres qui vous permettront d'en savoir plus:

• Edsger Wybe Dijkstra, W. H. J. Feijen : A Method of Programming
• Jon Bentley : Programming Pearls
• David Gries : The Science of Programming

Crédit : L'image en tête d'article est une photo de UX Indonesia sur Unsplash