Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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.

Fonti