Ricerca per interpolazione

Quando cerchi «Taylor» in un elenco telefonico, non lo apri a metà: lo apri verso la fine, perché la T viene tardi nell'alfabeto. La ricerca per interpolazione fa lo stesso con i numeri. Indovina dove dovrebbe trovarsi il valore cercato in base a quanto è grande, e con dati distribuiti in modo uniforme questa stima è sorprendentemente buona.

Una fila ordinata di barre con una linea dalla prima all'ultima barra, e il controllo posto dove l'altezza del valore cercato incontra quella linea
Una fila ordinata di barre con una linea dalla prima all'ultima barra, e il controllo posto dove l'altezza del valore cercato incontra quella linea

L'idea

La ricerca binaria controlla sempre il centro, qualunque cosa cerchi. La ricerca per interpolazione usa i valori. Se la parte rimasta della lista va da 10 a 100 e il valore cercato è 70, questo si trova a due terzi della distanza tra il primo e l'ultimo valore, quindi si controlla a due terzi della lista. In formula, il controllo avviene in lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Dopo il controllo si tiene la parte dal lato giusto, esattamente come nella ricerca binaria, e si stima di nuovo.

Due esempi

In 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, cercando 70 si controlla subito la posizione 7: trovato con 1 controllo, dove alla ricerca binaria ne servono 4. Ora prendi 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 e cerca 9. A causa del 999, ogni stima cade vicino all'inizio: la ricerca controlla 1, 2, 3 e così via, una posizione alla volta, e servono 9 controlli dove alla ricerca binaria ne servono 3.

Quanto è veloce

Quando i valori sono distribuiti in modo uniforme, o estratti a caso da una distribuzione uniforme, ogni controllo riduce la parte rimasta da circa n a circa √n. Questo dà in media circa log₂(log₂ n) controlli: circa 5 anche per un miliardo di valori, contro 30 per la ricerca binaria. Quando i valori sono distribuiti in modo molto irregolare, un controllo può escludere un solo valore, e il caso peggiore è di n controlli, male quanto la ricerca lineare. Ogni controllo costa anche una divisione, quindi in pratica conviene soprattutto quando i controlli sono costosi, come le letture da disco.

Storia e varianti

W. W. Peterson descrisse la ricerca per interpolazione nel 1957, per trovare record su memorie ad accesso diretto. La sua media di log log n per chiavi distribuite in modo uniforme fu dimostrata nel 1978 da Perl, Itai e Avni. Le versioni pratiche si proteggono dai dati sfavorevoli inserendo passi binari, per esempio la ricerca interpolazione-sequenziale o interpolazione-binaria, così che il caso peggiore resti vicino a log n.

Provala

Apri l'app, scegli un valore in «Cerca» e premi «Passo». Ogni controllo dice a che punto si trova il valore cercato tra i due valori alle estremità e a quale posizione corrisponde. Imposta «Distribuzione» su «Uniforme» e la maggior parte delle ricerche finisce con un controllo; impostala su «Asimmetrica» e i controlli avanzano lentamente all'inizio della lista. L'ultimo riquadro mostra quanti passi servirebbero alla ricerca binaria per lo stesso valore.

Domande frequenti

Qual è la complessità della ricerca per interpolazione?

O(log log n) in media per valori distribuiti in modo uniforme, e O(n) nel caso peggiore. Richiede O(1) memoria aggiuntiva e una lista ordinata.

Qual è la differenza tra ricerca per interpolazione e ricerca binaria?

La ricerca binaria controlla sempre il centro di ciò che resta. La ricerca per interpolazione controlla dove dovrebbe trovarsi il valore cercato, a giudicare dai valori alle due estremità. È molto meglio con valori distribuiti in modo uniforme e può essere molto peggio con valori asimmetrici.

Quali dati sono adatti alla ricerca per interpolazione?

Chiavi numeriche ordinate e distribuite in modo abbastanza uniforme: ID sequenziali con pochi buchi, timestamp di eventi regolari o chiavi hash. È adatta a dati in cui un controllo è costoso e un po' di aritmetica costa poco.

Perché l'app offre diverse distribuzioni?

Perché la distribuzione decide quanto sono buone le stime. Con valori uniformi la ricerca per interpolazione sembra quasi magica, mentre i valori asimmetrici ne mostrano il punto debole. Confrontarli con il conteggio della ricerca binaria è il modo più chiaro per capire quando usare l'una o l'altra.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova la ricerca per interpolazione