L'algorithme de recherche binaire
Tags: algorithms, programming, french
Published: 2021-07-19 19:45:00

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 {% katex inline %}a{% endkatex %} un tableau de taille {% katex inline %}N{% endkatex %}, avec des index {% katex inline %}0 \leq i < N{% endkatex %} et si {% katex inline %}x{% endkatex %} est un élément de ce tableau, trouver {% katex inline %}x{% endkatex %} dans {% katex inline %}a{% endkatex %} revient à trouver l'index {% katex inline %}i_x{% endkatex %} tel que {% katex inline %}a[i_x]{% endkatex %} soit égal à {% katex inline %}x{% endkatex %}.

{% katex %}
i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x
{% endkatex %}

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

{% katex %}
\forall i,j : 0 \leq i \leq j < N : a[i] \leq a[j] 
{% endkatex %}

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

{% katex %}
i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x \wedge a[i_x-1] < x
{% endkatex %}

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

{% katex %}
a[-1] = - \infty
{% endkatex %}

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

{% katex %}
a[N] = + \infty
{% endkatex %}

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

{% katex %}
i_x : 0 \leq x_i \leq N : a[i_x] \geq x \wedge a[i_x-1] < x
{% endkatex %}

Au début, l'intervalle de recherche est {% katex inline %}[0..N]{% endkatex %}, l'idée de l'algorithme de recherche binaire consiste à **réduire** cet intervalle à chaque itération afin de trouver {% katex inline %}i_x{% endkatex %}. Nous définissons l'intervalle de recherche à l'aide de deux nouvelles variables : {% katex inline %}L{% endkatex %} (pour _left_ ou _lower_) et {% katex inline %}R{% endkatex %} (pour _right_). Ces nouvelles variables devront en tout temps satisfaire l'invariant suivant:

{% katex %}
L,R : 0 \leq L < R \leq N : a[L] < x \wedge a[R] \geq x
{% endkatex %}

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

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

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

```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 {% katex inline %}x{% endkatex %} est présent dans {% katex inline %}a{% endkatex %} et retourner un `boolean`, on peut alors écrire

```python
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:

```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**](https://www.amazon.com/Method-Programming-English-Dutch/dp/0201175363)
- [Jon Bentley : **Programming Pearls**](https://www.amazon.com/Programming-Pearls-Jon-Bentley/dp/8177588583)
- [David Gries : **The Science of Programming**](https://www.springer.com/gp/book/9780387964805)

Crédit : L'image en tête d'article est une photo de [UX Indonesia](https://unsplash.com/@uxindo?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) sur [Unsplash](https://unsplash.com/s/photos/sorting?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)