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 connaître. Dans leur célèbre livre A Method Of Programming, Edsger W. Dijkstra et W.H.J. Feijen qualifient même cet al…

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 < N0i<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

.

ix:0≤xi<N:x∈a∧a[ix]=x
i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x
ix:0xi<N:xaa[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]

.

∀i,j:0≤i≤j<N:a[i]≤a[j]
\forall i,j : 0 \leq i \leq j < N : a[i] \leq a[j]
i,j:0ij<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

:

ix:0≤xi<N:x∈a∧a[ix]=x∧a[ix−1]<x
i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x \wedge a[i_x-1] < x
ix:0xi<N:xaa[ix]=xa[ix1]<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-1ix1

est égal à

−1-11

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-11

qui soit plus petit que tous les autres éléments du tableau:

a[−1]=−∞
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[N1]

, 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]=+∞
a[N] = + \infty
a[N]=+

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

ix:0≤xi≤N:a[ix]≥x∧a[ix−1]<x
i_x : 0 \leq x_i \leq N : a[i_x] \geq x \wedge a[i_x-1] < x
ix:0xiN:a[ix]xa[ix1]<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≤L<R≤N:a[L]<x∧a[R]≥x
L,R : 0 \leq L < R \leq N : a[L] < x \wedge a[R] \geq x
L,R:0L<RN:a[L]<xa[R]x

Pour commencer, nous pouvons initialiser

LLL

à

−1-11

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=R1

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:0xiN:a[R]xa[R1]<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<R1

, 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=R1

, 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<R1

, alors

L<h=⌊L+R2⌋<RL < h = \lfloor\frac{L+R}{2}\rfloor < RL<h=2L+R<R

. Si

L=R−1L = R-1L=R1

, 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:


Print Share Comment Cite Upload Translate
APA
Jacques Supcik | Sciencx (2024-03-29T12:36:18+00:00) » L’algorithme de recherche binaire. Retrieved from https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/.
MLA
" » L’algorithme de recherche binaire." Jacques Supcik | Sciencx - Monday July 19, 2021, https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/
HARVARD
Jacques Supcik | Sciencx Monday July 19, 2021 » L’algorithme de recherche binaire., viewed 2024-03-29T12:36:18+00:00,<https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/>
VANCOUVER
Jacques Supcik | Sciencx - » L’algorithme de recherche binaire. [Internet]. [Accessed 2024-03-29T12:36:18+00:00]. Available from: https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/
CHICAGO
" » L’algorithme de recherche binaire." Jacques Supcik | Sciencx - Accessed 2024-03-29T12:36:18+00:00. https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/
IEEE
" » L’algorithme de recherche binaire." Jacques Supcik | Sciencx [Online]. Available: https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/. [Accessed: 2024-03-29T12:36:18+00:00]
rf:citation
» L’algorithme de recherche binaire | Jacques Supcik | Sciencx | https://www.scien.cx/2021/07/19/lalgorithme-de-recherche-binaire/ | 2024-03-29T12:36:18+00:00
https://github.com/addpipe/simple-recorderjs-demo