L'algorithme de recherche binaire

Jacques Supcik - Jul 19 '21 - - Dev Community

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 aa un tableau de taille NN , avec des index 0i<N0 \leq i < N et si xx est un élément de ce tableau, trouver xx dans aa revient à trouver l'index ixi_x tel que a[ix]a[i_x] soit égal à xx .

ix:0xi<N:xaa[ix]=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 ii et jj , si ii est plus petit ou égal à jj alors a[i]a[i] est aussi plus petit ou égal à a[j]a[j] .

i,j:0ij<N:a[i]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é xx est présent plusieurs fois. Dans ce cas, nous aimerions avoir l'index du premier xx . Autrement dit, l'élément qui précède xx doit être strictement plus petit que xx :

ix:0xi<N:xaa[ix]=xa[ix1]<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 xx est le tout premier élément du tableau aa . Dans ce cas, ix1i_x-1 est égal à 1-1 et 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 qui soit plus petit que tous les autres éléments du tableau:

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

Nous sommes partis du principe que xx soit présent dans aa , mais nous pouvons lever cette contrainte en spécifiant que si xx n'est pas dans aa , alors on aimerait avoir l'index où il devrait être. Si xx est strictement plus petit que a[0]a[0] , alors le prédicat est satisfait en mettant ixi_x égal à 00 . Si xx est strictement plus grand que a[N1]a[N-1] , l'index où il devrait être c'est NN , mais 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] en définissant un nouvel élément virtuel à la position NN qui soit plus grand que tous les autres éléments du tableau:

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

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

ix:0xiN:a[ix]xa[ix1]<x 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][0..N] , l'idée de l'algorithme de recherche binaire consiste à réduire cet intervalle à chaque itération afin de trouver ixi_x . Nous définissons l'intervalle de recherche à l'aide de deux nouvelles variables : LL (pour left ou lower) et RR (pour right). Ces nouvelles variables devront en tout temps satisfaire l'invariant suivant:

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

Pour commencer, nous pouvons initialiser LL à 1-1 et RR à NN . Grâce à nos deux éléments virtuels, l'invariant est satisfait, car a[L]=<xa[L] = - \infty < x et a[R]=+xa[R] = + \infty \geq x . Il nous suffit maintenant de réduire l'intervalle ]L,R]]L,R] et quand LL sera juste à côté de RR , nous aurons L=R1L = R-1 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] < x et RR sera le ixi_x que nous cherchons.

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

Tant que L<R1L < R-1 , on peut toujours trouver un hh entre LL et RR . On peut par exemple prendre h=L+1h = L+1 ou h=R1h = R-1 , mais notre algorithme ne ferait que des tout petits pas vers la solution. Une manière plus efficace consiste à prendre hh au milieu de l'intervalle ]L,R]]L,R] , autrement dit h=L+R2h = \frac{L+R}{2} . hh est un index et doit être un nombre entier; nous devons alors arrondir hh vers un entier. On peut sans autre arrondir hh vers le haut ou vers le bas et nous décidons ici de l'arrondir vers le bas : h=L+R2h = \lfloor\frac{L+R}{2}\rfloor . Si L<R1L < R-1 , alors L<h=L+R2<RL < h = \lfloor\frac{L+R}{2}\rfloor < R . Si L=R1L = 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
Enter fullscreen mode Exit fullscreen mode

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 xx est présent dans aa 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
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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:

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

. . . . . . . . .