Interpolationssökning

När du slår upp ”Taylor” i en telefonkatalog öppnar du den inte i mitten: du öppnar den nära slutet, eftersom T kommer sent i alfabetet. Interpolationssökning gör samma sak med tal. Den gissar var målet bör stå utifrån hur stort det är, och på jämnt fördelade data är gissningen anmärkningsvärt bra.

En sorterad rad staplar med en linje från den första till den sista stapeln, och försöket placerat där målets höjd möter linjen
En sorterad rad staplar med en linje från den första till den sista stapeln, och försöket placerat där målets höjd möter linjen

Idén

Binärsökning tittar alltid i mitten, vad den än letar efter. Interpolationssökning använder värdena. Om den del av listan som återstår går från 10 till 100 och målet är 70, ligger målet två tredjedelar av vägen från det första värdet till det sista, så den tittar två tredjedelar in. Som formel ligger försöket på lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Efter försöket behåller den delen på rätt sida, precis som binärsökning, och uppskattar igen.

Två exempel

I 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 tittar en sökning efter 70 direkt på plats 7: hittat på 1 försök, där binärsökning behöver 4. Ta nu 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 och sök efter 9. På grund av 999 hamnar varje uppskattning nära början: sökningen tittar på 1, 2, 3 och så vidare, en plats i taget, och behöver 9 försök där binärsökning behöver 3.

Hur snabb den är

När värdena är jämnt fördelade, eller dragna slumpmässigt ur en jämn fördelning, krymper varje försök den del som återstår från ungefär n till ungefär √n. Det ger i genomsnitt ungefär log₂(log₂ n) försök: runt 5 även för en miljard värden, mot 30 för binärsökning. När värdena är mycket ojämnt fördelade kan ett försök ta bort så lite som ett värde, och i värsta fall behövs n försök, lika illa som linjär sökning. Varje försök kostar också en division, så i praktiken lönar den sig främst när försök är dyra, till exempel läsningar från disk.

Historia och varianter

W. W. Peterson beskrev interpolationssökning 1957, för att hitta poster i minne med direktåtkomst. Dess genomsnitt på log log n för jämnt fördelade nycklar bevisades 1978 av Perl, Itai och Avni. Praktiska versioner skyddar sig mot dåliga data genom att blanda in binära steg, till exempel interpolations-sekventiell sökning eller interpolations-binär sökning, så att värsta fallet håller sig nära log n.

Utforska den

Öppna appen, välj ett värde i Sök efter och tryck på Steg. Varje försök visar hur långt målet ligger mellan de två ändvärdena och vilken plats det pekar på. Växla Fördelning till Jämn så slutar de flesta sökningar efter ett försök; växla till Skev så kryper försöken längs början av listan. Den sista rutan visar hur många steg binärsökning skulle behöva för samma värde.

Ofta ställda frågor

Vad är tidskomplexiteten för interpolationssökning?

O(log log n) i genomsnitt för jämnt fördelade värden och O(n) i värsta fall. Den behöver O(1) extra minne och en sorterad lista.

Vad är skillnaden mellan interpolationssökning och binärsökning?

Binärsökning tittar alltid i mitten av det som återstår. Interpolationssökning tittar där målet bör stå, bedömt utifrån värdena i båda ändarna. Det är mycket bättre för jämnt fördelade värden och kan vara mycket sämre för skeva.

Vilka data passar för interpolationssökning?

Sorterade numeriska nycklar som är ganska jämnt fördelade: löpande id:n med få luckor, tidsstämplar för regelbundna händelser eller hashade nycklar. Den passar data där ett försök är dyrt och lite räkning är billigt.

Varför erbjuder appen olika fördelningar?

Eftersom fördelningen avgör hur bra uppskattningarna blir. Jämna värden får interpolationssökning att se nästan magisk ut, och skeva värden visar dess svaghet. Att jämföra dem med antalet för binärsökning är det tydligaste sättet att se när man ska använda vilken.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova interpolationssökning