Comprendre et intégrer la recherche binaire en JavaScript

Comprendre et intégrer la recherche binaire en JavaScript

Dans ce tutoriel, nous allons expliquer et intégrer le puissant algorithme qu’est la recherche binaire en JavaScript.

La recherche binaire ou dichotomique est le choix le plus approprié quand on a une séquence triée et qu’on veut trouver la position exacte d’un élément s’il existe au sein du tableau.

Sans plus tarder prenons l’exemple d’un tableau contenant la séquence de 60 nombres premiers avec leur index ou position indiqué sur le haut à droite de chaque cellule.

Capture d’écran 2021-06-07 à 10.24.42.png Disons que nous voulons savoir si le chiffre 181 existe dans ce tableau. Pour ce faire on définit une intervalle de recherche commençant au début du tableau ou à la position 0 et qui finit à la fin ou position 59 dans ce cas précis.

On calcule la position du milieu en déterminant le résultat de la somme arrondie de la position inférieure à la position supérieure divisée par 2 : (0 + 59) = 29,5 ou simplement 29.

On évalue la valeur trouvée à la position 29, 113, qui se trouve être inférieure à la valeur recherchée de 181. Cela devient très intéressant puisqu' on peut maintenant éliminer la valeur du milieu et tout le côté gauche du tableau qui comprend des valeurs moindres que celle que nous recherchions.

La prochaine étape consiste à incrémenter la position inférieure qui devient 30 et recommencer le même cycle: (30 + 59) / 2 = 44.5 ⇒ 44 La valeur à cette position, 197, est cette fois-ci plus grande que 181 donc on reprend le même processus d'élimination mais vers la droite cette fois puisque 197 et tout ce qui vient après seraient supérieurs à 181.

La position inférieure reste la même à 30 mais la position supérieure decrémente de 1 par rapport au milieu et devient 43.

Vous l’avez certainement deviné , on reprend le même cycle: (30 + 43) / 2 = 36.5 ⇒ 36 qui nous donne la valeur 157 - on élimine sur la gauche, incrémentons la position inférieure un fois de plus et faisons le même calcul: (37 + 43) / 2 = 40

40 ⇒ 179 ===> (41 + 43) / 2 = 42 ⇒ 191 ===> (41 + 41) / 2 = 41 ⇒ 181

bingo on a trouvé notre valeur et cela nous a pris 6 “lookups” or itérations pour en arriver là.

Si par contre on avait utilisé une recherche linéaire allant de la droite vers la gauche, ca nous aurait pris au moins 42 itérations pour le même résultat.

Maintenant qu’on a une solide idée du mécanisme, transformons notre cycle en code pour automatiser la recherche.

Nous allons donc mettre en place une fonction que l'on appelle binarySearch et qui va prendre comme paramètres un tableau arr et une valeur de recherche value.

On crée une variable min qui sera l'index inférieur et une variable max qui sera l'index supérieur.

On ajoute également guessIndex et tempValue qui nous permettra d’évaluer et de comparer avec value au cours des cycles.

Ajoutons la variable lookup qui va nous permettre simplement de documenter le nombre d'itérations.

Maintenant créons un boucle avec while qui aurait comme condition de test que max soit supérieur ou égal à min.

La valeur de guessIndex est l’entier inférieur de la somme min + plus max divisée par 2 et tempValue la valeur du tableau a cet index.

Par pure besoin de documentation, imprimons un message pour chaque itération indiquant l’intervalle et la valeur trouvée.

Maintenant on peut comparer tempValue et value et s’ils sont égaux, on peut terminer et quitter la boucle et envoyer un message de succès.

Le cas échéant, on regarde si tempValue est supérieure à value, on actualise le max index en décrémentant guessIndex.

Sinon si tempValue est inférieure à value, on actualise min index cette fois ci en incrémentant guessIndex.

Si aucune des conditions n’est satisfaite, on a pas trouvé la valeur qui correspond, on peut incrémenter les “lookup” et replonger dans la boucle.

Au final, si la condition de test se concrétise et qu’on a toujours pas trouvé la valeur correspondante, on peut déclarer en toute assurance que la valeur value n’existe pas dans le tableau arr.

Maintenant testons la fonction avec une petite mise en place,

D’abord exportons la fonction pour qu’elle soit utilisable comme module.

Créons un fichier package.json au même niveau et ajoutons une propriété type avec comme valeur module.

Et enfin dans un fichier de prépa binary-test, nous pouvons maintenant importer notre module binarySearch, renseigner un tableau avec 60 nombres premiers et faire appel à notre fonction pour effectuer la recherche de la valeur 181.

Nous pouvons essayer sur la ligne de commande en exécutant “node binary-test.js”, et on voit s’afficher les différents messages pour chaque itération et au final le message de renseignant le succès de la recherche et à quelle position la valeur à été trouvée.

Testons également le scénario avec une valeur non présente sur le tableau, disons 500 par exemple, et on voit que la même série de cycles est respectée avec le message approprié au final.

Voilà, c’est tout pour ce tuto. Nous espérons que cela vous a permis de comprendre et d’apprécier la puissance de cet algorithme quand il est exécuté dans le bon contexte.

Vous souhaitez un tuto sur un thème en particulier? Dites-nous tout en commentaires.