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 connatre. Dans leur clbre livre A Method Of Programming, Edsger W. Dijkstra et W.H.J. Feijen qualifient mme 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'implmenter 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 prdicats logiques et de vous permettre de l'implmenter de manire efficiente et correcte.

L'algorithme de recherche binaire permet de trouver efficacement un lment dans un tableau tri. Commenons par dfinir formellement ce qu'est la recherche d'un lment dans un tableau:

Si $a$ un tableau de taille $N$, avec des index $0i<N$ et si $x$ est un lment de ce tableau, trouver $x$ dans $a$ revient trouver l'index ixi_xix tel que a[ix]a[i_x]a[ix] soit gal $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]$.

Nous pouvons gnraliser l'objectif de la recherche dans le cas o l'lment recherch $x$ est prsent plusieurs fois. Dans ce cas, nous aimerions avoir l'index du premier $x$. Autrement dit, l'lment qui prcde $x$ doit tre strictement plus petit que $x$:

Cette nouvelle condition peut s'avrer problmatique si $x$ est le tout premier lment du tableau $a$. Dans ce cas, ix1i_x-1ix1 est gal $1$ et $a[1]$ n'est pas dfini. Nous pouvons rsoudre ce problme en dfinissant un lment virtuel la position $1$ qui soit plus petit que tous les autres lments du tableau:

Nous sommes partis du principe que $x$ soit prsent dans $a$, mais nous pouvons lever cette contrainte en spcifiant 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 prdicat est satisfait en mettant ixi_xix gal $0$. Si $x$ est strictement plus grand que $a[N1]$, l'index o il devrait tre c'est $N$, mais $a[N]$ n'est pas dfini.Nous contournons le problme de la mme manire que pour $a[1]$ en dfinissant un nouvel lment virtuel la position $N$ qui soit plus grand que tous les autres lments du tableau:

On peut rcrire le prdicat de la recherche ainsi:

Au dbut, l'intervalle de recherche est $[\mathrm{0..}N]$, l'ide de l'algorithme de recherche binaire consiste rduire cet intervalle chaque itration afin de trouver ixi_xix. Nous dfinissons 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:

Pour commencer, nous pouvons initialiser $L$ $1$ et $R$ $N$. Grce nos deux lments virtuels, l'invariant est satisfait, car $a[L]=<x$ et $a[R]=+x$. Il nous suffit maintenant de rduire l'intervalle $]L,R]$ et quand $L$ sera juste ct de $R$, nous aurons $L=R1$ et si l'invariant est toujours vrai, alors on aura R:0xiN:a[R]xa[R1]<xR : 0 \leq x_i \leq N : a[R] \geq x \wedge a[R-1] < xR:0xiN:a[R]xa[R1]<x et $R$ sera le ixi_xix que nous cherchons.

Avant de coder la recherche binaire, il nous faut encore juste trouver comment rduire 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<R1$, on peut toujours trouver un $h$ entre $L$ et $R$. On peut par exemple prendre $h=L+1$ ou $h=R1$, mais notre algorithme ne ferait que des tout petits pas vers la solution. Une manire plus efficace consiste prendre $h$ au milieu de l'intervalle $]L,R]$, autrement dit h=L+R2h = \frac{L+R}{2}h=2L+R. $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 dcidons ici de l'arrondir vers le bas : h=L+R2h = \lfloor\frac{L+R}{2}\rfloorh=2L+R. Si $L<R1$, alors L<h=L+R2<RL < h = \lfloor\frac{L+R}{2}\rfloor < RL<h=2L+R<R. Si $L=R1$, la recherche est termine et nous n'avons plus besoin de rduire l'intervalle.

Nous avons maintenant assez de logique et de math pour pouvoir crire un algorithme de recherche binaire correct. Pour cet article, nous dcidons 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 problme de dpassement de capacit (overflow) avec les entiers, mais la plupart des autres langages n'ont pas ce confort et l'opration L+R pourrait provoquer un dpassement de capacit. On pourrait alors sans autre remplacer h = (L+R) // 2 par h = L + (R-L) // 2 et ainsi supprimer le risque de dpassement de capacit.

Si on souhaite savoir si $x$ est prsent 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 complter, 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 trouvs sur Internet. Les programmeurs amateurs diront qu'il est inutile de comprendre les dtails des algorithmes fondamentaux, car ils ont dj t implments par des personnes trs comptentes et qu'il suffit d'utiliser la bonne bibliothque. L'informaticien qui se respecte ne peut se satisfaire d'une telle dmarche et sa saine curiosit ne sera satisfaite que lorsqu'il aura compris et implment lui-mme l'algorithme.

J'espre que cet article aura raviv la mmoire de certains et veill chez d'autres l'envie d'tudier plus en dtail 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