Hoppsökning

Hoppsökning är som att leta efter en sida i en bok utan innehållsförteckning: du bläddrar framåt en bit i taget och tittar på sidnumren, och när du har kommit för långt bläddrar du tillbaka genom den sista biten. I en sorterad lista kräver den betydligt färre jämförelser än att kontrollera varje värde.

En sorterad rad staplar uppdelad i block, där den sista stapeln i varje överhoppat block är bleknad och blocket som kan innehålla målet är skuggat
En sorterad rad staplar uppdelad i block, där den sista stapeln i varje överhoppat block är bleknad och blocket som kan innehålla målet är skuggat

Idén

I en sorterad lista visar det sista värdet i ett block om målet över huvud taget kan finnas i blocket: om det är mindre än målet är alla värden i blocket också mindre. Då behöver du inte titta inuti. Kontrollera det sista värdet i varje block i tur och ordning och hoppa över hela block, tills ett inte är mindre än målet. Då kan målet bara finnas i det blocket: gå igenom det från början.

Ett exempel

Sök efter 23 i 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 med block om 3. Det första blocket slutar på 8, som är mindre, så hoppa över det. Det andra blocket slutar på 23, som inte är mindre, så 23 kan bara finnas bland 12, 16, 23. Genomgången ger 12, 16 och sedan 23: hittat efter 5 jämförelser, där linjär sökning behöver 6 och binärsökning 3. Vid sökning efter 40 leder blockens slutvärden 8, 23 och 72 till blocket 38, 56, 72; 38 är mindre och 56 redan större, så 40 finns inte där: återigen 5 jämförelser.

Varför √n

Med block om m värden krävs högst ungefär n/m jämförelser för att hitta rätt block och högst m för att gå igenom det. Få, långa hopp gör genomgången lång; många korta hopp gör hoppandet långt. Summan n/m + m är minst när båda delarna är lika, vid m = √n, där den är ungefär 2√n. För 40 värden betyder det block om 6 och högst 13 jämförelser; för en miljon värden block om 1 000 och ungefär 2 000 jämförelser.

Var den passar in

Binärsökning behöver färre jämförelser, ungefär log₂ n. Men binärsökning hoppar fram och tillbaka över hela listan, medan hoppsökning bara går framåt och backar en gång, till början av ett block. Det gjorde den attraktiv för data på band eller i en länkad struktur där det är långsamt att gå tillbaka. Ben Shneiderman beskrev den som jump searching 1978. Samma idé att dela upp i √n block, ofta kallad kvadratrotsuppdelning, finns i många andra algoritmer.

Ben Shneiderman (till vänster) med Catherine Plaisant på Webshop 2012. Shneiderman beskrev hopsökning 1978.
Ben Shneiderman (till vänster) med Catherine Plaisant på Webshop 2012. Shneiderman beskrev hopsökning 1978.

Utforska den

Öppna appen, välj ett värde i Sök efter och tryck på Steg. Varje hopp markerar det sista värdet i ett block; överhoppade block bleknar, och blocket som kan innehålla målet är skuggat medan det gås igenom. Ändra Hopplängd från √n till 2 eller 8 med 40 staplar och se balansen mellan hopp och genomgång förskjutas.

Ofta ställda frågor

Vilken tidskomplexitet har hoppsökning?

O(√n) med block om √n värden: högst ungefär 2√n jämförelser. Den behöver O(1) extra minne och en sorterad lista.

Vad är skillnaden mellan hoppsökning och binärsökning?

Binärsökning halverar den återstående delen varje gång och behöver ungefär log₂ n jämförelser, men går fram och tillbaka. Hoppsökning hoppar framåt i fasta steg och går igenom ett block, behöver ungefär 2√n jämförelser och backar bara en gång.

Kan genomgången av det sista blocket använda binärsökning i stället?

Ja. Med binärsökning i blocket minskar genomgången från m jämförelser till ungefär log₂ m. Hoppen kostar fortfarande n/m, så då lönar sig större block.

Kräver hoppsökning en sorterad lista?

Ja. Att hoppa över ett block är bara säkert eftersom ett mindre sista värde betyder att alla värden i blocket är mindre. Appen sorterar en osorterad lista först.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova hoppsökning