Recherche binaire en JavaScript

La recherche binaire est un algorithme de recherche utilisé pour trouver la position d'un élément spécifique dans une liste triée. Cela fonctionne en divisant à plusieurs reprises la liste en deux, jusqu'à ce que l'élément souhaité soit trouvé ou qu'il soit déterminé que l'élément n'est pas présent dans la liste.

Comment fonctionne la recherche binaire ?

Pour comprendre comment fonctionne la recherche binaire, considérons un exemple. Supposons que nous ayons une liste triée d'entiers et que nous voulions trouver la position du nombre 37. Voici comment l'algorithme de recherche binaire fonctionnerait :

1. Tout d'abord, nous déterminons l'élément du milieu de la liste. Si l'élément du milieu est 37, nous avons terminé et nous renvoyons la position de l'élément.
2. Si l'élément du milieu n'est pas 37, nous vérifions s'il est supérieur ou inférieur à 37. S'il est supérieur à 37, nous savons que l'élément souhaité doit être dans la moitié gauche de la liste. S'il est inférieur à 37, nous savons que l'élément recherché doit se trouver dans la moitié droite de la liste.
3. Nous répétons le processus sur la moitié appropriée de la liste jusqu'à ce que l'élément soit trouvé ou qu'il soit déterminé que l'élément n'est pas présent dans la liste.

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

Pourquoi devrions-nous utiliser la recherche binaire ?

Alors, pourquoi devrions-nous utiliser la recherche binaire ? L'un des principaux avantages de la recherche binaire est sa complexité temporelle. Dans le pire des cas, la complexité temporelle de la recherche binaire est O(log n), ce qui signifie qu'elle est beaucoup plus rapide que la recherche linéaire (O(n)) pour les grandes listes. Cela en fait un algorithme efficace pour rechercher de grands ensembles de données.

En conclusion, la recherche binaire est un algorithme utile pour trouver rapidement la position d'un élément spécifique dans une liste triée. Sa complexité temporelle le rend adapté à la recherche de grands ensembles de données et il est relativement facile à implémenter en JavaScript.