CKTIS / JavaScript
Ricerca lineare
La ricerca lineare controlla gli elementi di un array in ordine finché trova una corrispondenza o raggiunge la fine. Non serve che l’array sia ordinato; la funzione mostrata restituisce l’indice della prima corrispondenza oppure -1.
Versione: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Sintassi
function linearSearch(array, target) {
for (var i = 0; i < array.length; i++) {
if (array[i] === target) return i;
}
return -1;
}La ricerca lineare (linear search) è un algoritmo, non una parola chiave di JavaScript. Controlla gli elementi in sequenza, partendo dall’indice 0, e si ferma alla prima corrispondenza. L’array non deve essere ordinato. linearSearch(array, target) restituisce l’indice dell’elemento corrispondente oppure -1, anche se l’array è vuoto.
L’esempio usa ===: non converte i tipi, quindi il numero 8 non corrisponde al testo "8". NaN non corrisponde nemmeno a NaN, e gli oggetti corrispondono solo se sono lo stesso oggetto. La funzione non modifica l’array. L’esempio presuppone un array ordinario, senza posizioni vuote, che non cambia durante la ricerca.
Per n elementi, nel caso peggiore servono n confronti: il tempo è O(n) e lo spazio aggiuntivo è O(1), supponendo che letture e confronti abbiano costo costante. Una corrispondenza immediata richiede un tempo O(1). Controlla il risultato con index !== -1, non con if (index): l’indice valido 0 è falsy, mentre -1 è truthy.
Anche il metodo integrato array.indexOf(target) restituisce il primo indice usando il confronto stretto, ma ignora le proprietà di indice mancanti; il ciclo mostrato le legge e di solito ottiene undefined. L’algoritmo non appartiene a una specifica edizione di ECMAScript; l’esempio usa una sintassi disponibile in ES3 e non richiede né Web APIs né metodi moderni degli array.
Esempi
function linearSearch(array, target) {
for (var i = 0; i < array.length; i++) {
if (array[i] === target) return i;
}
return -1;
}
var values = [8, 3, 8, 5];
console.log(linearSearch(values, 8));
console.log(linearSearch(values, 5));
console.log(linearSearch(values, 9));
console.log(linearSearch([], 8));Risultato
0 3 -1 -1
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.