Sammenligninger
Springlængde
Lineær søgning ville kræve

  • Mål
  • Aktiv blok
  • Sammenlignet
  • Udelukket
  • Fundet

Mere om springsøgning

Springsøgning

Springsøgning ligger mellem lineær og binær søgning. Den går gennem en sorteret liste i spring på m pladser og tjekker kun den sidste værdi i hver blok, indtil den når en blok, hvis sidste værdi ikke er mindre end målet. Så gennemgår den blokken fra starten. Vælg værdien og springlængden, og se, hvor mange sammenligninger springene og gennemgangen kræver. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå én sammenligning 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 den aktive blok. Springsøgning kræver en sorteret liste, så en usorteret liste sorteres først. Vælg værdien, springlængden, 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

  1. Vælg den værdi, du vil søge efter, springlængden og hvor mange søjler. Eller skriv dine egne tal: springsøgning sorterer dem først.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil i søgningen.
  3. Prøv en springlængde på 2 og på 8 med 40 søjler, og sammenlign antallet af sammenligninger med √n.

Sådan virker springsøgning

Del den sorterede liste i blokke på m værdier. Se på den sidste værdi i den første blok. Er den mindre end målet, kan målet ikke være nogen steder i den blok, så spring til slutningen af næste blok, og se igen. Så snart en bloks sidste værdi ikke er mindre, kan målet kun være i den blok: gå tilbage til dens start, og tjek værdierne én ad gangen, indtil du finder målet eller passerer det.

Valg af springlængde

Med n værdier kræver springene op til n/m sammenligninger og gennemgangen op til m. Små spring gør gennemgangen kort, men springene mange; store spring gør det modsatte. Summen n/m + m er mindst, når m = √n, hvilket giver omkring 2√n sammenligninger: højst 13 for 40 værdier, mod 40 for lineær søgning og 6 for binær søgning. Springsøgning går aldrig mere end én blok tilbage, hvilket hjælper, når det er langsomt at gå baglæns gennem dataene.

Ofte stillede spørgsmål

Hvordan virker springsøgning?

På en sorteret liste springer den frem i skridt på m pladser og tjekker den sidste værdi i hver blok. Når den værdi ikke længere er mindre end målet, kan målet kun være i den blok, som den så gennemgår fra starten.

Hvad er den bedste springlængde?

√n, afrundet. Springene koster op til n/m sammenligninger og gennemgangen op til m, og summen er mindst, når de to er lige store, ved m = √n. Det giver omkring 2√n sammenligninger i værste fald.

Er springsøgning hurtigere end binær søgning?

Nej, binær søgning kræver færre sammenligninger: omkring log₂ n mod omkring 2√n. Springsøgning kan stadig vinde, når det er dyrt at gå tilbage gennem dataene, fordi den kun går tilbage én gang, til starten af én blok.

Hvilket match finder den, når værdier gentages?

Det første. Hver blok, den springer over, slutter med en værdi, der er mindre end målet, så ingen tidligere blok kan indeholde et match, og gennemgangen starter ved begyndelsen af blokken.

Bliver mine tal sendt nogen steder hen?

Nej. Søgningen kører i din browser, og dine seneste indstillinger gemmes 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