Jämförelser
Hopplängd
Linjär sökning skulle behöva

  • Mål
  • Aktivt block
  • Jämförda
  • Uteslutna
  • Hittade

Mer om hoppsökning

Hoppsökning

Hoppsökning ligger mellan linjär sökning och binärsökning. Den går igenom en sorterad lista i hopp om m platser och kontrollerar bara det sista värdet i varje block, tills den når ett block vars sista värde inte är mindre än målet. Sedan går den igenom det blocket från början. Välj värdet och hopplängden, och se hur många jämförelser hoppen och genomgången kräver. Tryck på Spela för att se sökningen, eller använd Steg och Bakåt för att gå en jämförelse 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 det aktiva blocket. Hoppsökning kräver en sorterad lista, så en osorterad lista sorteras först. Välj värdet, hopplängden, 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, hopplängden och hur många staplar. Eller skriv dina egna tal: hoppsökning sorterar dem först.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa vart som helst i sökningen.
  3. Prova hopplängd 2 och 8 med 40 staplar, och jämför antalet jämförelser med √n.

Så fungerar hoppsökning

Dela upp den sorterade listan i block om m värden. Titta på det sista värdet i det första blocket. Om det är mindre än målet kan målet inte finnas någonstans i det blocket, så hoppa till slutet av nästa block och titta igen. Så snart ett blocks sista värde inte är mindre kan målet bara finnas i det blocket: gå tillbaka till dess början och kontrollera värdena ett i taget tills du hittar målet eller passerar det.

Välja hopplängd

Med n värden kräver hoppen upp till n/m jämförelser och genomgången upp till m. Korta hopp gör genomgången kort men hoppen många; långa hopp gör tvärtom. Summan n/m + m är minst när m = √n, vilket ger ungefär 2√n jämförelser: högst 13 för 40 värden, mot 40 för linjär sökning och 6 för binärsökning. Hoppsökning går aldrig tillbaka mer än ett block, vilket hjälper när det är långsamt att gå bakåt i datan.

Ofta ställda frågor

Hur fungerar hoppsökning?

I en sorterad lista hoppar den framåt i steg om m platser och kontrollerar det sista värdet i varje block. När det värdet inte längre är mindre än målet kan målet bara finnas i det blocket, som den då går igenom från början.

Vilken hopplängd är bäst?

√n, avrundat. Hoppen kostar upp till n/m jämförelser och genomgången upp till m, och summan är minst när de två är lika, vid m = √n. Det ger ungefär 2√n jämförelser i värsta fall.

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

Nej, binärsökning behöver färre jämförelser: ungefär log₂ n mot ungefär 2√n. Hoppsökning kan ändå vinna när det är dyrt att gå tillbaka i datan, eftersom den bara backar en gång, till början av ett block.

Vilken träff hittar den när värden upprepas?

Den första. Varje block den hoppar över slutar med ett värde som är mindre än målet, så inget tidigare block kan innehålla en träff, och genomgången börjar i början av blocket.

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