Recherche Binaire Javascript

Michael Zippo 04.11.2021

Comment coder une recherche binaire en JavaScript

Les algorithmes de recherche facilitent grandement la vie d`un programmeur. Cela facilite la recherche d`un élément particulier dans un ensemble de données de dizaines, de centaines ou de milliers d`éléments.

L`une des formes de recherche les plus populaires est la recherche binaire. Cette recherche trouve rapidement un élément dans un tableau. Chaque fois que la recherche examine un élément, elle divise par deux le nombre d`éléments à trouver.

Dans ce guide, nous parlerons de ce que sont les recherches binaires et de leur fonctionnement. Ensuite, nous passerons à la mise en œuvre d`une recherche binaire en utilisant deux approches différentes : itérative et récursive.

Construisons un algorithme de recherche binaire en !

Qu`est-ce qu`une recherche binaire ?

Une recherche binaire est un algorithme informatique qui recherche un élément dans un tableau ordonné.

Commencez au milieu d`un tableau et vérifiez si l`élément du milieu est inférieur, égal ou supérieur au nombre que vous recherchez.

Si le nombre est inférieur, l`algorithme sait continuer à chercher dans la moitié gauche du tableau, là où se trouvent les plus petits nombres ; si le nombre est supérieur, l`algorithme se concentrera sur la moitié droite du tableau. Les recherches binaires ne fonctionnent que sur des listes ordonnées.

Les recherches binaires sont plus efficaces que les recherches linéaires. En effet, à chaque fois qu`une recherche est effectuée, le nombre d`éléments restant à trouver dans la liste est réduit de moitié.

Comment utiliser une recherche binaire

Une recherche binaire est facile à comprendre une fois que vous l`avez apprise.

Avant de mettre en œuvre un algorithme de recherche binaire, passons en revue - faisons un pas. On trouvera le nombre « 9 » dans une liste. Commençons par une liste ordonnée :

6 < / td>

Tout d`abord, nous devons trouver le nombre du milieu et l`affecter à une variable. Ceci est trouvé en calculant la somme du premier et du dernier nombre et en divisant par deux. Nous appellerons cette variable "centrale" :

Début	< br>	Moyen		Fin
2	6	8	9	10

8 est notre nombre moyen. Ainsi, nous pouvons comparer le nombre central avec celui que nous recherchons. Si le nombre central est le même que celui que nous recherchons, notre recherche peut s`arrêter.

Dans cet exemple, 8 n`est pas égal à 9. Notre recherche continue.

Nous devons donc comparer si le nombre au milieu est supérieur à 9. Ce n`est pas le cas.

Cela nous indique que le nombre que nous recherchons doit être après le centre nombre. 9 est supérieur à 8 dans une liste ordonnée. définissez notre numéro de départ pour qu`il soit égal au nombre central. En effet, nous savons que le nombre que nous recherchons ne vient pas avant le nombre central.

Si le nombre que nous recherchons est plus bébé, nous définirons le nombre final comme étant égal au nombre du milieu. Puisque le nombre est plus petit que le nombre du milieu, nous pourrions concentrer notre recherche sur la moitié inférieure de la liste.

La recherche binaire se répète dans la moitié supérieure de la liste car 9 est supérieur à 8 :

< td> Moyenne

Start Fin

8 < /td>

Recherchons le numéro central. C`est 9. Nous pouvons comparer 9 avec le nombre que nous recherchons. 9 est égal au nombre que nous recherchons.

Cela signifie que nos recherches peuvent s`arrêter. Nous avons réussi à trouver le numéro 9 sur notre liste !

Comment implémenter une recherche binaire en JavaScript

Les recherches binaires peuvent être implémentées à l`aide d`une approche itérative ou récursive.

Recherche binaire itérative

Une recherche binaire itérative utilise une boucle while pour trouver un élément dans une liste. Cette boucle s`exécutera jusqu`à ce que l`élément soit trouvé dans la liste ou jusqu`à ce que la liste ait été recherchée.

Commençons par écrire un fonction qui effectue notre recherche binaire :

Commençons par définir deux variables : début et fin. Ceux-ci gardent une trace des valeurs les plus élevées et les plus basses sur lesquelles notre recherche travaille. Nous utilisons une boucle while qui s`exécute jusqu`à ce que le numéro de début soit supérieur au numéro de fin. Cette boucle calcule le nombre intermédiaire entre le début et la fin de la liste.

Si le nombre que nous recherchons est égal au nombre du milieu, le nombre du milieu est renvoyé à notre programme principal. Si le nombre est plus petit, la valeur de départ est définie pour être égale au nombre du milieu plus 1. Ces comparaisons sont effectuées à l`aide d`une instruction if .

Sinon, le nombre final est défini comme étant le nombre du milieu moins un. Si notre nombre n`est pas trouvé après l`exécution de la boucle while, il renvoie -1. Nous l`appelons la condition de base. Dans notre programme principal, nous Je vais vérifier si le nombre renvoyé est égal à -1. Cela signifie que notre numéro n`a pas été trouvé.

Notre fonction ne fonctionne pas encore. Nous devons écrire un programme principal pour le nommer :

Nous avons défini une liste de numéros à rechercher et le numéro que nous voulons trouver dans notre liste. Ensuite, nous avons appelé la fonction binarySearch. Cela fera notre recherche. La recherche renverra -1 ou la position de l`élément que nous recherchons.

-1 indique qu`un élément n`a pu être trouvé. Si un élément n`est pas trouvé, le contenu de notre instruction else est exécuté. Sinon, le contenu de l`instruction if est exécuté.

Exécutons notre code :

Cela nous indique que notre recherche a réussi !

Recherche binaire récursive

Une recherche binaire récursive est considérée comme plus élégante qu`une recherche itérative. En effet, les recherches binaires effectuent la même opération encore et encore sur une liste. Ce comportement peut être implémenté à l`aide d`un algorithme de récursivité.

Ouvrez un nouveau fichier JavaScript et collez ce code :

Ce code fait les mêmes comparaisons que notre première recherche. Vérifiez si le nombre du milieu est égal, supérieur ou inférieur au nombre que nous recherchons.

Au début de notre fonction , nous avons utilisé une instruction if pour vérifier si le numéro de départ est supérieur au numéro de fin. Si c`est le cas, cela signifie que notre élément n`a pas été trouvé dans la liste que nous avons spécifiée. Dans ce cas, nous renvoyons -1 au programme principal.

Si le numéro que nous recherchons est le même que le numéro central, le numéro central est renvoyé au programme principal. Si le nombre que nous recherchons est supérieur ou inférieur au nombre central, notre fonction de recherche binaire est exécutée à nouveau. Cela continue jusqu`à ce que notre élément soit trouvé.

Pour exécuter cette fonction, nous devrons apporter une modification à notre programme principal :

Nous devons passer deux paramètres supplémentaires : les valeurs ‚Äã‚Äãode "start" et "end". La valeur de "start" est égale à 0. La valeur de "end" est égale à la longueur de la liste moins un.

Exécutons notre code et voyons ce qui se passe :

Notre recherche binaire a réussi ! Il utilise le même algorithme sous-jacent que l`approche itérative. La différence est que la recherche binaire est effectuée à l`aide d`une fonction appelée jusqu`à ce que l`élément soit trouvé ou jusqu`à ce que la recherche dans la liste soit terminée, selon la première éventualité.

Conclusion

Les recherches binaires facilitent la recherche d`un élément dans une liste. Chaque fois qu`une recherche est effectuée, le nombre d`éléments restant à trouver dans une liste est réduit de moitié. Cela rend une recherche binaire plus efficace qu`une recherche linéaire.

Vous êtes maintenant prêt à implémentez la recherche binaire en JavaScript comme un expert !