Jämförelser
Fortfarande möjliga
Binärsökning skulle behöva

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

Mer om exponentiell sökning

Exponentiell sökning

Exponentiell sökning hittar ett värde i en sorterad lista i två faser. Först tittar den på plats 1, 2, 4, 8, 16 och så vidare och dubblar varje gång, tills värdet där inte är mindre än målet. Sedan binärsöker den sträckan mellan de två sista platserna. Välj värdet att söka efter och se varför mål nära början hittas med bara några få jämförelser. 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. Exponentiell sökning kräver en sorterad lista, så en osorterad lista sorteras först. Välj värdet, 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 och hur många staplar. Eller skriv dina egna tal: exponentiell sö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. Sök efter ett värde nära början och ett nära slutet, och jämför antalet med Binärsökning skulle behöva.

Så fungerar exponentiell sökning

Titta på värdet på plats 1. Om det är mindre än målet, titta på plats 2, sedan 4, 8, 16, och dubbla varje gång. Så fort ett värde inte är mindre stannar du: målet kan bara ligga efter den förra platsen du tittade på och före den här. Binärsök den sträckan. Om dubbleringen går förbi listans slut, binärsök från den sista platsen du tittade på till slutet.

Snabb nära början, och ingen längd behövs

För att nå ett mål på plats i behöver dubbleringen ungefär log₂ i kontroller, och sträckan den hittar rymmer färre än i värden, så binärsökningen behöver ungefär log₂ i till. Det blir ungefär 2 log₂ i totalt, vilket beror på var målet finns, inte på hur lång listan är. Mål nära början hittas snabbare än med vanlig binärsökning; mål nära slutet kostar upp till ungefär dubbelt så mycket. Eftersom den aldrig behöver listans längd fungerar den också på listor som är för långa att mäta eller saknar känt slut.

Ofta ställda frågor

Hur fungerar exponentiell sökning?

I en sorterad lista kontrollerar den plats 1, 2, 4, 8 och så vidare tills värdet där inte är mindre än målet. Då kan målet bara ligga mellan de två sista kontrollerade platserna, och en binärsökning i den sträckan hittar det.

Är exponentiell sökning snabbare än binärsökning?

När målet är nära listans början, ja: ett mål på plats i kräver ungefär 2 log₂ i jämförelser, oavsett listans längd. När målet är nära slutet är vanlig binärsökning snabbare, med upp till ungefär en faktor två.

Vad används den till?

Till att söka i listor vars längd är okänd eller obegränsad, som en dataström eller en oändlig följd, och till att slå samman sorterade sekvenser, där nästa träff oftast ligger nära. Timsorts galloping-läge använder samma idé med dubblering.

Varför kallas den exponentiell?

Eftersom platserna den kontrollerar växer exponentiellt: 1, 2, 4, 8, 16, var och en dubbelt så stor som den förra. Den kallas också dubbleringssökning eller galloping search.

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