Recherche dichotomique en JavaScript

Introduction

Dans ce laboratoire, nous allons explorer les bases de la programmation JavaScript. Nous aborderons des sujets tels que les variables, les types de données, les fonctions et le flux de contrôle. À la fin du laboratoire, vous aurez une compréhension solide de la syntaxe JavaScript et serez capable d'écrire des programmes de base en utilisant ce langage. Ce laboratoire est conçu pour les débutants ayant peu ou pas d'expérience de programmation, mais il sera également utile pour ceux qui souhaitent rafraîchir leurs connaissances sur JavaScript.

Skills Graph

Algorithme de recherche dichotomique

Pour commencer la pratique de codage, ouvrez le Terminal/SSH et tapez node. L'algorithme de recherche dichotomique est utilisé pour trouver l'index d'un élément donné dans un tableau trié. Voici les étapes pour implémenter l'algorithme de recherche dichotomique :

1. Décarez les limites de recherche gauche et droite, l et r, initialisées à 0 et à la longueur du tableau respectivement.
2. Utilisez une boucle while pour réduire progressivement le sous-tableau de recherche en le divisant par deux à l'aide de Math.floor().
3. Si l'élément est trouvé, renvoyez son index. Sinon, renvoyez -1.
4. Notez que cet algorithme ne prend pas en compte les valeurs dupliquées dans le tableau.

Voici une implémentation exemple de l'algorithme de recherche dichotomique en JavaScript :

const binarySearch = (arr, item) => {
  let l = 0,
    r = arr.length - 1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    const guess = arr[mid];
    if (guess === item) return mid;
    if (guess > item) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
};

Vous pouvez tester la fonction binarySearch avec les exemples suivants :

binarySearch([1, 2, 3, 4, 5], 1); // 0
binarySearch([1, 2, 3, 4, 5], 5); // 4
binarySearch([1, 2, 3, 4, 5], 6); // -1

Sommaire

Félicitations ! Vous avez terminé le laboratoire de Recherche dichotomique. Vous pouvez pratiquer d'autres laboratoires sur LabEx pour améliorer vos compétences.