Implémentation de la recherche binaire en JavaScript

Vous effectuez une recherche dans un tableau trié de 100 000 prix de produits. La méthode native indexOf() de JavaScript vérifie chaque élément depuis le début — cela représente potentiellement 100 000 comparaisons. La recherche binaire le fait en 17 comparaisons maximum. Cette différence explique pourquoi l’algorithme de recherche binaire en JavaScript est important, et pourquoi il vaut la peine de l’implémenter soi-même — car JavaScript ne fournit aucune méthode native de recherche binaire.

Cet article explique le fonctionnement de la recherche binaire, comment implémenter les versions itérative et récursive, et quand l’utiliser plutôt qu’une recherche linéaire.

Qu’est-ce que la recherche binaire et pourquoi nécessite-t-elle un tableau trié ?

La recherche binaire est un algorithme de type diviser pour régner. Elle fonctionne en divisant répétitivement l’espace de recherche par deux jusqu’à trouver la valeur cible ou épuiser toutes les possibilités.

Voici le piège : elle ne fonctionne que sur des tableaux triés. L’algorithme suppose que si la cible est supérieure à l’élément du milieu, elle doit se trouver dans la moitié droite. Cette hypothèse s’effondre complètement sur des données non triées — vous obtiendriez des résultats erronés sans aucune erreur.

Les étapes sont :

1. Trouver l’élément du milieu de la plage de recherche actuelle
2. S’il est égal à la cible, retourner son index
3. Si la cible est plus petite, rechercher dans la moitié gauche
4. Si la cible est plus grande, rechercher dans la moitié droite
5. Répéter jusqu’à ce qu’elle soit trouvée ou que la plage de recherche soit vide

Implémentation de la recherche binaire en JavaScript : approche itérative

La version itérative utilise une boucle while et deux pointeurs. C’est l’approche préférable dans la plupart des cas — lisible, efficace et utilisant un espace O(1).

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)

    if (arr[mid] === target) {
      return mid // Return the index
    } else if (arr[mid] < target) {
      start = mid + 1 // Search right half
    } else {
      end = mid - 1 // Search left half
    }
  }

  return -1 // Target not found
}

const prices = [10, 25, 47, 89, 134, 200]
console.log(binarySearch(prices, 89))  // 3
console.log(binarySearch(prices, 50))  // -1

Notez que cette fonction retourne l’index de la cible, et non un booléen. C’est presque toujours plus utile en pratique.

Recherche binaire récursive en JavaScript

La version récursive transmet des indices de limites mis à jour à chaque appel. Elle est élégante mais utilise un espace de pile O(log n) — une frame par appel récursif.

function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, end)
    : binarySearchRecursive(arr, target, start, mid - 1)
}

const scores = [3, 11, 22, 45, 67, 91]
console.log(binarySearchRecursive(scores, 22))  // 2
console.log(binarySearchRecursive(scores, 50))  // -1

Un bug courant : oublier de faire un return de l’appel récursif. Sans cela, la fonction retourne undefined même lorsque l’élément existe.

Trier avant de rechercher

Si votre tableau n’est pas déjà trié, vous devez le trier d’abord. Le Array.sort() par défaut de JavaScript trie lexicographiquement, ce qui casse les comparaisons numériques :

[10, 9, 100].sort()                   // [10, 100, 9] — incorrect
[10, 9, 100].sort((a, b) => a - b)    // [9, 10, 100] — correct

Utilisez toujours un comparateur numérique pour les tableaux de nombres avant d’exécuter une recherche binaire.

Recherche binaire vs recherche linéaire : quand utiliser laquelle ?

Pour un tableau de 10 000 éléments, la recherche linéaire nécessite jusqu’à 10 000 comparaisons. La recherche binaire en nécessite 14 au maximum. Si vous effectuez une seule recherche dans un petit tableau non trié, indexOf() convient. Si vous effectuez des recherches répétées dans de grandes données triées, la recherche binaire est l’outil approprié.

Conclusion

La recherche binaire est simple à implémenter en JavaScript une fois que vous comprenez l’exigence de tableau trié. Utilisez la version itérative par défaut — elle est plus claire et évite la surcharge de la pile d’appels. Utilisez la version récursive lorsque la structure de votre code en bénéficie, mais n’oubliez pas de toujours faire un return de l’appel récursif. Et vérifiez toujours que votre tableau est trié avec un comparateur numérique approprié avant de rechercher.

FAQ

Complete picture for complete understanding

Capture every clue your frontend is leaving so you can instantly get to the root cause of any issue with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data.

Check our GitHub repo and join the thousands of developers in our community.