Interpolationssøgning

Når du slår »Taylor« op i en telefonbog, åbner du den ikke på midten: du åbner den bagerst, fordi T kommer sent i alfabetet. Interpolationssøgning gør det samme med tal. Den gætter, hvor målet bør stå, ud fra hvor stort det er, og på jævnt fordelte data er det gæt bemærkelsesværdigt godt.

En sorteret række søjler med en linje fra den første til den sidste søjle, og opslaget placeret, hvor målets højde møder linjen
En sorteret række søjler med en linje fra den første til den sidste søjle, og opslaget placeret, hvor målets højde møder linjen

Idéen

Binær søgning slår altid op i midten, uanset hvad den leder efter. Interpolationssøgning bruger værdierne. Går den del af listen, der er tilbage, fra 10 til 100, og er målet 70, ligger målet to tredjedele af vejen fra den første værdi til den sidste, så den slår op to tredjedele inde. Som formel ligger opslaget på lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Efter opslaget beholder den delen på den rigtige side, præcis som binær søgning, og skønner igen.

To eksempler

I 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 slår en søgning efter 70 straks op på plads 7: fundet med 1 opslag, hvor binær søgning skal bruge 4. Tag nu 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 og søg efter 9. På grund af 999 lander hvert skøn nær starten: søgningen slår op på 1, 2, 3 og så videre, én plads ad gangen, og skal bruge 9 opslag, hvor binær søgning skal bruge 3.

Hvor hurtig den er

Når værdierne er jævnt fordelt eller trukket tilfældigt fra en jævn fordeling, skrumper hvert opslag den del, der er tilbage, fra cirka n til cirka √n. Det giver i gennemsnit omkring log₂(log₂ n) opslag: cirka 5 selv for en milliard værdier mod 30 med binær søgning. Når værdierne er meget ujævnt fordelt, kan et opslag fjerne så lidt som én værdi, og i værste fald kræves n opslag, lige så dårligt som lineær søgning. Hvert opslag koster også en division, så i praksis betaler den sig mest, når opslag er dyre, for eksempel læsninger fra disk.

Historie og varianter

W. W. Peterson beskrev interpolationssøgning i 1957 til at finde poster i lager med direkte adgang. Gennemsnittet på log log n for jævnt fordelte nøgler blev bevist i 1978 af Perl, Itai og Avni. Praktiske udgaver beskytter sig mod dårlige data ved at blande binære trin ind, for eksempel interpolations-sekventiel søgning eller interpolations-binær søgning, så det værste tilfælde holder sig tæt på log n.

Udforsk den

Åbn appen, vælg en værdi i Søg efter, og tryk på Trin. Hvert opslag fortæller, hvor langt målet ligger mellem de to endeværdier, og hvilken plads det peger på. Skift Fordeling til Jævn, og de fleste søgninger slutter efter ét opslag; skift den til Skæv, og opslagene kryber langs starten af listen. Det sidste felt viser, hvor mange trin binær søgning ville kræve for den samme værdi.

Ofte stillede spørgsmål

Hvad er tidskompleksiteten af interpolationssøgning?

O(log log n) i gennemsnit for jævnt fordelte værdier og O(n) i værste fald. Den kræver O(1) ekstra hukommelse og en sorteret liste.

Hvad er forskellen på interpolationssøgning og binær søgning?

Binær søgning slår altid op i midten af det, der er tilbage. Interpolationssøgning slår op, hvor målet bør stå, bedømt ud fra værdierne i begge ender. Det er meget bedre på jævnt fordelte værdier og kan være meget dårligere på skæve.

Hvilke data passer til interpolationssøgning?

Sorterede numeriske nøgler, der er nogenlunde jævnt fordelt: fortløbende id'er med få huller, tidsstempler for regelmæssige hændelser eller hashede nøgler. Den passer til data, hvor et opslag er dyrt og lidt regning er billigt.

Hvorfor tilbyder appen forskellige fordelinger?

Fordi fordelingen afgør, hvor gode skønnene er. Jævne værdier får interpolationssøgning til at virke næsten magisk, og skæve værdier viser dens svaghed. At sammenligne dem med antallet for binær søgning er den klareste måde at se, hvornår man skal bruge hvad.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Prøv interpolationssøgning