Algorithmes JavaScript: recherche binaire

La recherche binaire suppose que le tableau (ou toute autre structure de données) dans lequel vous effectuez la recherche est ordonné.

Nous commençons par le tableau et l'élément que nous devons rechercher.

Nous regardons le milieu du tableau. Nous prenons le nombre d'éléments et nous le divisons par 2. Imaginons que nous ayons une partie du tableau à gauche et l'autre partie à droite.

Si l'élément que nous avons est inférieur à celui que nous recherchons, alors il doit être dans la bonne partie, afin que nous puissions complètement supprimer la partie de droite.

Ensuite, nous effectuons la même action, divisant la partie droite du tableau en 2, en regardant l'élément du milieu, et nous jetons une partie du tableau.

En fin de compte, vous obtiendrez l'article (ou vous retournereznullsi l'élément n'est pas trouvé).

Au final, si le tableau contenait 8 éléments, nous trouvons l'élément en au plus 4 étapes.

Si le tableau contenait 32 éléments, nous avons un maximum de 6 étapes dans le pire des cas. Comparé à 32 en recherche linéaire, c'est une énorme optimisation!

La recherche binaire aO(log n) complexité.

Voici une implémentation possible de celui-ci:

const binarySearch = (list, item) => {
  let low = 0
  let high = list.length - 1

while (low <= high) { const mid = Math.floor((low + high) / 2) const guess = list[mid]

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">===</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">mid</span>
}

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">&gt;</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#a6e22e">high</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
} <span style="color:#66d9ef">else</span> {
  <span style="color:#a6e22e">low</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
}

}

return null //if not found }

Comment cela marche-t-il? Nous obtenons lelistarray et la valeur de l'élément que nous recherchons. Ensuite, nous initialisons lelowvaleur à 0 initialement, et lehighvaleur au dernier index de la liste. Nous regardons d'abord l'élément du milieu, et si c'est ce que nous recherchons, nous le retournons, et nous avons terminé. Sinon, nous définissons lelowouhighvaleurs pour ne regarder que la partie gauche ou droite du tableau, et nous répétons le processus jusqu'à ce que nous trouvions l'élément.

Nous retournons l'index de l'élément dans le tableau:

console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

Nous retournonsnullsi l'élément n'est pas trouvé:

console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

Téléchargez mon gratuitManuel du débutant JavaScript


Plus de tutoriels js: