Ricerca: ricerca lineare e binaria

Per trovare un nome in una lista ordinata di un milione, la ricerca binaria non ha mai bisogno di più di 20 controlli.

Cercare un valore

La ricerca è il problema di trovare dove si trova un valore in una raccolta, o di scoprire che non c'è. Lo fa il tuo telefono quando digiti il nome di un contatto, lo fa un negozio quando controlla se un articolo è disponibile, e lo fa un correttore ortografico per ogni parola che scrivi. L'input è una lista e un valore cercato. L'output è la posizione del valore cercato, oppure un segnale come -1 che significa «non trovato».

Ricerca lineare: uno alla volta

Il metodo più semplice è partire da sinistra e controllare un valore dopo l'altro finché trovi l'obiettivo o la lista finisce. Questa è la ricerca lineare. Funziona su qualsiasi lista, ordinata o no. Il suo costo dipende dalla fortuna: se l'obiettivo è il primo, basta un controllo; se è l'ultimo o manca, controlli ogni valore. Per una lista di n valori il caso peggiore è di n controlli. Una lista lunga il doppio può richiedere il doppio dei controlli, ed è da qui che viene il nome «lineare»: il lavoro cresce in linea retta con la dimensione.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // trovato
  }
  return -1;                             // controllato tutto
}

Ricerca binaria: dimezza quello che resta

Se la lista è ordinata, puoi fare molto meglio. Pensa al gioco dell'indovina il numero: qualcuno sceglie un numero da 1 a 100 e risponde solo «più alto» o «più basso». Un giocatore furbo prova prima 50. Qualunque sia la risposta, metà delle possibilità sparisce. Il tentativo successivo è il centro di ciò che resta, e così via. La ricerca binaria fa esattamente questo con una lista ordinata. Tiene due indicatori, lo e hi, attorno alla parte in cui l'obiettivo potrebbe ancora trovarsi. Controlla il valore centrale. Se è l'obiettivo, ha finito. Se il valore centrale è più piccolo dell'obiettivo, anche tutto ciò che sta alla sua sinistra è più piccolo, quindi lo si sposta oltre il centro. Se è più grande, hi si sposta prima del centro. Quando lo supera hi, non resta nulla e l'obiettivo non è nella lista.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // obiettivo a destra
    else hi = mid - 1;                     // obiettivo a sinistra
  }
  return -1;
}

Quanti controlli?

Ogni controllo della ricerca binaria almeno dimezza la parte che resta. Partendo da n valori, dopo un controllo ne restano al massimo circa n/2, dopo due circa n/4, e così via finché resta un solo valore. Il numero di dimezzamenti necessari per passare da n a 1 è il logaritmo in base 2 di n, scritto log₂ n. Contando anche l'ultimo controllo, la ricerca binaria richiede al massimo ⌊log₂ n⌋ + 1 controlli, dove ⌊ ⌋ significa arrotondare per difetto. Per 100 valori sono 7 controlli, ed è per questo che il gioco dell'indovina il numero si può sempre vincere in 7 tentativi. Per 1000 valori sono 10, per un milione (1000000) 20 e per un miliardo 30.

Il limite: la lista deve essere ordinata

La ricerca binaria funziona solo perché, in una lista ordinata, un confronto ti dice da quale parte deve trovarsi l'obiettivo. In una lista non ordinata il valore centrale non dice nulla dei suoi vicini, quindi torni alla ricerca lineare. Ordinare richiede a sua volta lavoro (le prossime due unità parlano proprio di questo), quindi la scelta dipende dall'uso. Se cerchi in una lista una volta sola, la ricerca lineare può essere la più economica. Se cerchi nella stessa lista migliaia di volte, ordinarla una volta e poi usare la ricerca binaria conviene presto. Questo scambio tra preparare i dati e rispondere alle domande su di essi attraversa tutta la materia.