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
aaa
un tableau de taille
NNN
, avec des index
0≤i<N0 \leq i < N0≤i<N
et si
xxx
est un élément de ce tableau, trouver
xxx
dans
aaa
revient à trouver l’index
ixi_xix
tel que
a[ix]a[i_x]a[ix]
soit égal à
xxx
.
i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x
ix:0≤xi<N:x∈a∧a[ix]=x
Nous avons aussi dit que le tableau est trié (du plus petit au plus grand). Ca signifie que pour tout
iii
et
jjj
, si
iii
est plus petit ou égal à
jjj
alors
a[i]a[i]a[i]
est aussi plus petit ou égal à
a[j]a[j]a[j]
.
\forall i,j : 0 \leq i \leq j < N : a[i] \leq a[j]
∀i,j:0≤i≤j<N:a[i]≤a[j]
Nous pouvons généraliser l’objectif de la recherche dans le cas où l’élément recherché
xxx
est présent plusieurs fois. Dans ce cas, nous aimerions avoir l’index du premier
xxx
. Autrement dit, l’élément qui précède
xxx
doit être strictement plus petit que
xxx
:
i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x \wedge a[i_x-1] < x
ix:0≤xi<N:x∈a∧a[ix]=x∧a[ix−1]<x
Cette nouvelle condition peut s’avérer problématique si
xxx
est le tout premier élément du tableau
aaa
. Dans ce cas,
ix−1i_x-1ix−1
est égal à
−1-1−1
et
a[−1]a[-1]a[−1]
n’est pas défini. Nous pouvons résoudre ce problème en définissant un élément virtuel à la position
−1-1−1
qui soit plus petit que tous les autres éléments du tableau:
a[-1] = – \infty
a[−1]=−∞
Nous sommes partis du principe que
xxx
soit présent dans
aaa
, mais nous pouvons lever cette contrainte en spécifiant que si
xxx
n’est pas dans
aaa
, alors on aimerait avoir l’index où il devrait être. Si
xxx
est strictement plus petit que
a[0]a[0]a[0]
, alors le prédicat est satisfait en mettant
ixi_xix
égal à
000
. Si
xxx
est strictement plus grand que
a[N−1]a[N-1]a[N−1]
, l’index où il devrait être c’est
NNN
, mais
a[N]a[N]a[N]
n’est pas défini.Nous contournons le problème de la même manière que pour
a[−1]a[-1]a[−1]
en définissant un nouvel élément virtuel à la position
NNN
qui soit plus grand que tous les autres éléments du tableau:
a[N] = + \infty
a[N]=+∞
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
ix:0≤xi≤N:a[ix]≥x∧a[ix−1]<x
Au début, l’intervalle de recherche est
[0..N][0..N][0..N]
, l’idée de l’algorithme de recherche binaire consiste à réduire cet intervalle à chaque itération afin de trouver
ixi_xix
. Nous définissons l’intervalle de recherche à l’aide de deux nouvelles variables :
LLL
(pour left ou lower) et
RRR
(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
L,R:0≤L<R≤N:a[L]<x∧a[R]≥x
Pour commencer, nous pouvons initialiser
LLL
à
−1-1−1
et
RRR
à
NNN
. Grâce à nos deux éléments virtuels, l’invariant est satisfait, car
a[L]=−∞<xa[L] = – \infty < xa[L]=−∞<x
et
a[R]=+∞≥xa[R] = + \infty \geq xa[R]=+∞≥x
. Il nous suffit maintenant de réduire l’intervalle
]L,R]]L,R]]L,R]
et quand
LLL
sera juste à côté de
RRR
, nous aurons
L=R−1L = R-1L=R−1
et si l’invariant est toujours vrai, alors on aura
R:0≤xi≤N:a[R]≥x∧a[R−1]<xR : 0 \leq x_i \leq N : a[R] \geq x \wedge a[R-1] < xR:0≤xi≤N:a[R]≥x∧a[R−1]<x
et
RRR
sera le
ixi_xix
que nous cherchons.
Avant de coder la recherche binaire, il nous faut encore juste trouver comment réduire l’intervalle
]L,R]]L,R]]L,R]
tout en conservant l’invariant. La solution consiste à prendre un
hhh
n’importe où entre
LLL
et
RRR
(
L<h<RL < h < RL<h<R
) et si
a[h]a[h]a[h]
est strictement plus petit que
xxx
, alors nous pouvons donner à
LLL
la valeur de
hhh
, car
a[L]a[L]a[L]
serait strictement plus petit que
xxx
comme nous ne modifions pas
RRR
, l’invariant tiendrait toujours. Au contraire, si
a[h]a[h]a[h]
est plus grand ou égal à
xxx
, alors nous pouvons donner à
RRR
la valeur de
hhh
, car
a[R]a[R]a[R]
serait plus grand ou égal à
xxx
comme nous ne modifions pas
LLL
, l’invariant tiendrait encore.
Tant que
L<R−1L < R-1L<R−1
, on peut toujours trouver un
hhh
entre
LLL
et
RRR
. On peut par exemple prendre
h=L+1h = L+1h=L+1
ou
h=R−1h = R-1h=R−1
, mais notre algorithme ne ferait que des tout petits pas vers la solution. Une manière plus efficace consiste à prendre
hhh
au milieu de l’intervalle
]L,R]]L,R]]L,R]
, autrement dit
h=L+R2h = \frac{L+R}{2}h=2L+R
.
hhh
est un index et doit être un nombre entier; nous devons alors arrondir
hhh
vers un entier. On peut sans autre arrondir
hhh
vers le haut ou vers le bas et nous décidons ici de l’arrondir vers le bas :
h=⌊L+R2⌋h = \lfloor\frac{L+R}{2}\rfloorh=⌊2L+R⌋
. Si
L<R−1L < R-1L<R−1
, alors
L<h=⌊L+R2⌋<RL < h = \lfloor\frac{L+R}{2}\rfloor < RL<h=⌊2L+R⌋<R
. Si
L=R−1L = R-1L=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
xxx
est présent dans
aaa
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