Implementazione di ricerca binaria in JavaScript
Livello 5421 battiture
binarySearch cerca un valore in un array ordinato controllando l'elemento centrale e dimezzando l'intervallo a ogni passo. Stampa 3 per 7, -1 per 8 (assente) e 0 per 1.
Codice JavaScript
// Restituisce l'indice di target nell'array ordinato arr, oppure -11function binarySearch(arr, target) { // L'intervallo di ricerca è all'inizio l'intero array: indici da 0 a length - 12 let left = 0;3 let right = arr.length - 1;4 // Ripete finché l'intervallo contiene almeno un elemento5 while (left <= right) { // Indice dell'elemento centrale, arrotondato per difetto6 const mid = Math.floor((left + right) / 2);7 // L'elemento centrale è target: ne restituisce l'indice8 if (arr[mid] === target) return mid; // Il centro è troppo piccolo, quindi target può stare solo nella metà destra9 if (arr[mid] < target) left = mid + 1; // Il centro è troppo grande, quindi la ricerca prosegue nella metà sinistra10 else right = mid - 1;11 }12 // L'intervallo è vuoto: target non è nell'array13 return -1;14}15 // La ricerca binaria funziona solo su un array ordinato come questo16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];// 7 viene trovato al primo centro, l'indice 3, quindi stampa 317console.log(binarySearch(sorted, 7));// 8 non è nell'array, quindi stampa -118console.log(binarySearch(sorted, 8));// 1 è il primo elemento, quindi stampa 019console.log(binarySearch(sorted, 1));Output
3 -1 0
Esercitati a digitare questo codice. I risultati non vengono registrati in classifica.
Simboli in questo codice
I simboli che digiti in questo codice JavaScript e quante volte compaiono.
(× 12)× 12,× 11;× 11=× 10.× 5-× 3[× 3]× 3{× 2