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 -11function binarySearch(arr, target) { // L'intervalle de recherche est d'abord tout le tableau : indices 0 à length - 12 let left = 0;3 let right = arr.length - 1;4 // Boucle tant que l'intervalle contient au moins un élément5 while (left <= right) { // Indice de l'élément du milieu, arrondi vers le bas6 const mid = Math.floor((left + right) / 2);7 // L'élément du milieu est target : renvoie son indice8 if (arr[mid] === target) return mid; // Le milieu est trop petit, target ne peut donc être que dans la moitié droite9 if (arr[mid] < target) left = mid + 1; // Le milieu est trop grand, la recherche continue donc dans la moitié gauche10 else right = mid - 1;11 }12 // L'intervalle est vide : target n'est pas dans le tableau13 return -1;14}15 // La recherche binaire ne fonctionne que sur un tableau trié comme celui-ci16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];// 7 est trouvé dès le premier milieu, l'indice 3, donc la ligne affiche 317console.log(binarySearch(sorted, 7));// 8 n'est pas dans le tableau, donc la ligne affiche -118console.log(binarySearch(sorted, 8));// 1 est le premier élément, donc la ligne affiche 019console.log(binarySearch(sorted, 1));Sortie
3 -1 0
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