- Mål
- Stadig mulige
- Sammenlignet
- Udelukket
- Fundet
Interpolationssøgning
Interpolationssøgning leder efter en værdi i en sorteret liste, som når du slår op i en telefonbog: for et navn, der begynder med T, slår du op bagerst, ikke i midten. Den skønner målets plads ud fra værdierne i begge ender af den del, der er tilbage. Vælg værdien og hvordan værdierne er fordelt, gå gennem opslagene trin for trin, og se, hvornår skønnet slår binær søgning, og hvornår det ikke gør. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå ét trin ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Den stiplede linje markerer den værdi, du søger efter, og den skraverede del er, hvor den stadig kan være. Interpolationssøgning kræver en sorteret liste, så en usorteret liste sorteres først. Vælg værdien, hvordan værdierne er fordelt, hvor mange søjler, eller skriv dine egne tal. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.
Sådan virker det
- Vælg den værdi, der skal søges efter, hvordan værdierne er fordelt, og hvor mange søjler. Eller skriv dine egne tal: interpolationssøgning sorterer dem først.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå ét trin ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i søgningen.
- Skift Fordeling mellem Jævn, Tilfældige huller og Skæv, og sammenlign Opslag med Binær søgning ville kræve.
Sådan virker interpolationssøgning
Kig på den første og sidste værdi i den del af den sorterede liste, der stadig kan rumme målet. Ligger målet for eksempel 40 % af vejen fra den første værdi til den sidste, så slå op på pladsen 40 % inde. Er værdien der målet, er du færdig. Er den mindre, er kun pladserne efter den tilbage; er den større, kun pladserne før den. Skøn igen i det, der er tilbage. Er målet mindre end den første værdi eller større end den sidste, er det der ikke.
Hvornår skønnet virker
Er værdierne jævnt fordelt, som 10, 20, 30 og så videre, rammer det første skøn målet eller kommer meget tæt på, og søgningen kræver i gennemsnit omkring log₂(log₂ n) opslag: cirka 5 for en milliard værdier mod 30 med binær søgning. Klumper værdierne sig sammen, som 1, 2, 3, 4, 1000, lander skønnene hele tiden forkert, og hvert opslag fjerner måske kun én værdi, så i værste fald kræves n opslag. Binær søgning klarer sig aldrig dårligere end omkring log₂ n.
Ofte stillede spørgsmål
Hvordan virker interpolationssøgning?
I en sorteret liste skønner den, hvor målet bør stå, ud fra den første og sidste værdi i den del, der er tilbage, slår op på den plads og beholder kun delen på den rigtige side. Det er som binær søgning med et klogere gæt end midten.
Er interpolationssøgning hurtigere end binær søgning?
Med jævnt fordelte værdier, ja: i gennemsnit omkring log₂(log₂ n) opslag i stedet for omkring log₂ n. Med ujævnt fordelte værdier kan den være meget langsommere, op til n opslag, mens binær søgning aldrig kræver mere end omkring log₂ n.
Hvorfor kan den være langsom?
Fordi skønnet antager, at værdierne vokser jævnt. Er de fleste værdier små og nogle få enorme, lander skønnet for et lille mål nær starten igen og igen og fjerner kun en eller to værdier hver gang.
Hvor bruges interpolationssøgning?
Hvor nøglerne er næsten jævnt fordelt og opslag er dyre, for eksempel når man slår poster op efter numerisk id eller hash på disk. Mange systemer kombinerer den med binær søgning for at bevare et godt værste tilfælde.
Bliver mine tal sendt nogen steder hen?
Nej. Søgningen kører i din browser, og dine seneste indstillinger bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor