Försök
Fortfarande möjliga
Binärsökning skulle behöva

  • Mål
  • Fortfarande möjliga
  • Jämförda
  • Uteslutna
  • Hittade

Mer om interpolationssökning

Interpolationssökning

Interpolationssökning letar efter ett värde i en sorterad lista på samma sätt som du slår upp i en telefonkatalog: för ett namn som börjar på T öppnar du nära slutet, inte i mitten. Den uppskattar målets plats utifrån värdena i båda ändarna av den del som återstår. Välj värdet och hur värdena är fördelade, stega genom försöken och se när uppskattningen slår binärsökning och när den inte gör det. Tryck på Spela för att se sökningen, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa vart som helst. Den streckade linjen markerar värdet du söker efter, och den skuggade delen är där det fortfarande kan finnas. Interpolationssökning kräver en sorterad lista, så en osorterad lista sorteras först. Välj värdet, hur värdena är fördelade, hur många staplar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Välj värdet att söka efter, hur värdena är fördelade och hur många staplar. Eller skriv dina egna tal: interpolationssökning sorterar dem först.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst i sökningen.
  3. Växla Fördelning mellan Jämn, Slumpade luckor och Skev, och jämför Försök med Binärsökning skulle behöva.

Så fungerar interpolationssökning

Titta på det första och sista värdet i den del av den sorterade listan som fortfarande kan innehålla målet. Om målet till exempel ligger 40 % av vägen från det första värdet till det sista, titta på platsen 40 % in. Är värdet där målet är du klar. Är det mindre återstår bara platserna efter det; är det större, bara platserna före det. Uppskatta igen i det som återstår. Är målet mindre än det första värdet eller större än det sista finns det inte där.

När uppskattningen fungerar

Om värdena är jämnt fördelade, som 10, 20, 30 och så vidare, hamnar den första uppskattningen på målet eller mycket nära det, och sökningen behöver i genomsnitt ungefär log₂(log₂ n) försök: runt 5 för en miljard värden, mot 30 för binärsökning. Om värdena klumpar ihop sig, som 1, 2, 3, 4, 1000, hamnar uppskattningarna hela tiden fel och varje försök tar kanske bara bort ett värde, så i värsta fall behövs n försök. Binärsökning klarar sig aldrig sämre än ungefär log₂ n.

Ofta ställda frågor

Hur fungerar interpolationssökning?

I en sorterad lista uppskattar den var målet bör stå utifrån det första och sista värdet i den del som återstår, tittar på den platsen och behåller bara delen på rätt sida. Det är som binärsökning med en smartare gissning än mitten.

Är interpolationssökning snabbare än binärsökning?

Med jämnt fördelade värden, ja: i genomsnitt ungefär log₂(log₂ n) försök i stället för ungefär log₂ n. Med ojämnt fördelade värden kan den vara mycket långsammare, upp till n försök, medan binärsökning aldrig behöver mer än ungefär log₂ n.

Varför kan den vara långsam?

Eftersom uppskattningen förutsätter att värdena växer jämnt. Om de flesta värden är små och några få enorma hamnar uppskattningen för ett litet mål nära början gång på gång och tar bara bort ett eller två värden varje gång.

Var används interpolationssökning?

Där nycklarna är nästan jämnt fördelade och försök är dyra, till exempel när man slår upp poster efter numeriskt id eller hash på disk. Många system kombinerar den med binärsökning för att behålla ett bra värsta fall.

Skickas mina tal någonstans?

Nej. Sökningen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

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

Gå till Editor