- Mål
- Stadig mulige
- Sammenlignet
- Udelukket
- Fundet
Eksponentiel søgning
Eksponentiel søgning finder en værdi i en sorteret liste i to faser. Først kigger den på plads 1, 2, 4, 8, 16 og så videre og fordobler hver gang, indtil værdien der ikke er mindre end målet. Derefter søger den binært i stykket mellem de sidste to pladser. Vælg den værdi, der skal søges efter, og se, hvorfor mål tæt på starten findes med blot få sammenligninger. 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 der, hvor den stadig kan være. Eksponentiel søgning kræver en sorteret liste, så en usorteret liste sorteres først. Vælg værdien, 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, og hvor mange søjler. Eller skriv dine egne tal: eksponentiel sø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.
- Søg efter en værdi tæt på starten og en tæt på slutningen, og sammenlign antallet med Binær søgning ville kræve.
Sådan virker eksponentiel søgning
Kig på værdien på plads 1. Hvis den er mindre end målet, så kig på plads 2, derefter 4, 8, 16, med fordobling hver gang. Så snart en værdi ikke er mindre, stopper du: målet kan kun ligge efter den forrige plads, du kiggede på, og før denne. Søg binært i det stykke. Hvis fordoblingen løber forbi listens slutning, så søg binært fra den sidste plads, du kiggede på, til slutningen.
Hurtig nær starten, og ingen længde nødvendig
For at nå et mål på plads i kræver fordoblingen omkring log₂ i kig, og det stykke, den finder, rummer færre end i værdier, så den binære søgning kræver omkring log₂ i mere. Det er omkring 2 log₂ i i alt, og det afhænger af, hvor målet er, ikke af hvor lang listen er. Mål tæt på starten findes hurtigere end med almindelig binær søgning; mål tæt på slutningen koster op til omkring dobbelt så meget. Fordi den aldrig har brug for listens længde, virker den også på lister, der er for lange til at måle eller ikke har nogen kendt slutning.
Ofte stillede spørgsmål
Hvordan virker eksponentiel søgning?
I en sorteret liste tjekker den plads 1, 2, 4, 8 og så videre, indtil værdien der ikke er mindre end målet. Så kan målet kun ligge mellem de sidste to tjekkede pladser, og en binær søgning i det stykke finder det.
Er eksponentiel søgning hurtigere end binær søgning?
Når målet er tæt på starten af listen, ja: et mål på plads i kræver omkring 2 log₂ i sammenligninger, uanset listens længde. Når målet er tæt på slutningen, er almindelig binær søgning hurtigere, med op til omkring en faktor to.
Hvad bruges den til?
Til at søge i lister, hvis længde er ukendt eller ubegrænset, som en datastrøm eller en uendelig følge, og til at flette sorterede sekvenser, hvor det næste match som regel er tæt på. Timsorts galloping-tilstand bruger samme idé med fordobling.
Hvorfor hedder den eksponentiel?
Fordi de pladser, den tjekker, vokser eksponentielt: 1, 2, 4, 8, 16, hver dobbelt så stor som den forrige. Den kaldes også fordoblingssøgning eller galloping search.
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