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 -1
1function binarySearch(arr, target) {
// L'intervallo di ricerca è all'inizio l'intero array: indici da 0 a length - 1
2 let left = 0;
3 let right = arr.length - 1;
4
// Ripete finché l'intervallo contiene almeno un elemento
5 while (left <= right) {
// Indice dell'elemento centrale, arrotondato per difetto
6 const mid = Math.floor((left + right) / 2);
7
// L'elemento centrale è target: ne restituisce l'indice
8 if (arr[mid] === target) return mid;
// Il centro è troppo piccolo, quindi target può stare solo nella metà destra
9 if (arr[mid] < target) left = mid + 1;
// Il centro è troppo grande, quindi la ricerca prosegue nella metà sinistra
10 else right = mid - 1;
11 }
12
// L'intervallo è vuoto: target non è nell'array
13 return -1;
14}
15
// La ricerca binaria funziona solo su un array ordinato come questo
16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
// 7 viene trovato al primo centro, l'indice 3, quindi stampa 3
17console.log(binarySearch(sorted, 7));
// 8 non è nell'array, quindi stampa -1
18console.log(binarySearch(sorted, 8));
// 1 è il primo elemento, quindi stampa 0
19console.log(binarySearch(sorted, 1));

Output

3
-1
0
Esercitati a digitare questo codice

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

Altri esempi JavaScript di livello 5

← Pratica di digitazione JavaScript