This content originally appeared on DEV Community and was authored by Jacques Supcik
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 .
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] .
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 :
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:
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:
On peut récrire le prédicat de la recherche ainsi:
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:
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
This content originally appeared on DEV Community and was authored by Jacques Supcik
Jacques Supcik | Sciencx (2021-07-19T19:45:34+00:00) L’algorithme de recherche binaire. Retrieved from https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.