Implémentation de recherche binaire en JavaScript

Niveau 5421 frappes

binarySearch cherche une valeur dans un tableau trié en examinant l'élément du milieu et en divisant l'intervalle par deux à chaque étape. Elle affiche 3 pour 7, -1 pour 8 (absent) et 0 pour 1.

Code JavaScript

// Renvoie l'indice de target dans le tableau trié arr, ou -1
1function binarySearch(arr, target) {
// L'intervalle de recherche est d'abord tout le tableau : indices 0 à length - 1
2 let left = 0;
3 let right = arr.length - 1;
4
// Boucle tant que l'intervalle contient au moins un élément
5 while (left <= right) {
// Indice de l'élément du milieu, arrondi vers le bas
6 const mid = Math.floor((left + right) / 2);
7
// L'élément du milieu est target : renvoie son indice
8 if (arr[mid] === target) return mid;
// Le milieu est trop petit, target ne peut donc être que dans la moitié droite
9 if (arr[mid] < target) left = mid + 1;
// Le milieu est trop grand, la recherche continue donc dans la moitié gauche
10 else right = mid - 1;
11 }
12
// L'intervalle est vide : target n'est pas dans le tableau
13 return -1;
14}
15
// La recherche binaire ne fonctionne que sur un tableau trié comme celui-ci
16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
// 7 est trouvé dès le premier milieu, l'indice 3, donc la ligne affiche 3
17console.log(binarySearch(sorted, 7));
// 8 n'est pas dans le tableau, donc la ligne affiche -1
18console.log(binarySearch(sorted, 8));
// 1 est le premier élément, donc la ligne affiche 0
19console.log(binarySearch(sorted, 1));

Sortie

3
-1
0
S'entraîner à taper ce code

Entraînez-vous à taper ce code. Les résultats ne sont pas enregistrés dans le classement.

Symboles de ce code

Les symboles que vous tapez dans ce code JavaScript et leur nombre d'occurrences.

  • (× 12
  • )× 12
  • ,× 11
  • ;× 11
  • =× 10
  • .× 5
  • -× 3
  • [× 3
  • ]× 3
  • {× 2

Autres exemples JavaScript de niveau 5

← Entraînement à la frappe JavaScript