Sprongzoeken

Sprongzoeken is hoe je een bladzijde zoekt in een boek zonder inhoudsopgave: je bladert telkens een stuk vooruit en kijkt naar de paginanummers, en zodra je te ver bent, blader je het laatste stuk terug door. In een gesorteerde lijst kost het veel minder vergelijkingen dan elke waarde controleren.

Een gesorteerde rij staven verdeeld in blokken, de laatste staaf van elk overgeslagen blok vervaagd en het blok waar het doel in kan staan gearceerd
Een gesorteerde rij staven verdeeld in blokken, de laatste staaf van elk overgeslagen blok vervaagd en het blok waar het doel in kan staan gearceerd

Het idee

In een gesorteerde lijst vertelt de laatste waarde van een blok of het doel überhaupt in dat blok kan staan: is die kleiner dan het doel, dan is elke waarde in het blok ook kleiner. Je hoeft er dus niet in te kijken. Controleer om de beurt de laatste waarde van elk blok en sla hele blokken over, tot er een niet kleiner is dan het doel. Dan kan het doel alleen in dat blok staan: doorloop het vanaf het begin.

Een voorbeeld

Zoek 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, met blokken van 3. Het eerste blok eindigt op 8, dat kleiner is, dus sla het over. Het tweede blok eindigt op 23, dat niet kleiner is, dus 23 kan alleen in 12, 16, 23 staan. Dat doorlopen geeft 12, 16 en dan 23: gevonden na 5 vergelijkingen, waar lineair zoeken er 6 nodig heeft en binair zoeken 3. Bij zoeken naar 40 leiden de blokeinden 8, 23 en 72 naar het blok 38, 56, 72; 38 is kleiner en 56 al groter, dus 40 staat er niet in: weer 5 vergelijkingen.

Waarom √n

Bij blokken van m waarden kost het vinden van het juiste blok hoogstens ongeveer n/m vergelijkingen en het doorlopen ervan hoogstens m. Weinig, lange sprongen maken het doorlopen lang; veel korte sprongen maken het springen lang. De som n/m + m is het kleinst als beide delen gelijk zijn, bij m = √n, waar ze ongeveer 2√n is. Bij 40 waarden betekent dat blokken van 6 en hoogstens 13 vergelijkingen; bij een miljoen waarden blokken van 1.000 en ongeveer 2.000 vergelijkingen.

Waar het past

Binair zoeken heeft minder vergelijkingen nodig, ongeveer log₂ n. Maar binair zoeken springt heen en weer door de hele lijst, terwijl sprongzoeken alleen vooruitgaat en één keer terugstapt, naar het begin van één blok. Daardoor was het aantrekkelijk voor data op tape of in een gelinkte structuur waar teruggaan traag is. Ben Shneiderman beschreef het in 1978 als jump searching. Hetzelfde idee van opdelen in √n blokken, vaak vierkantswortel-decompositie genoemd, komt in veel andere algoritmen terug.

Ben Shneiderman (links) met Catherine Plaisant op Webshop 2012. Shneiderman beschreef de sprongzoektocht in 1978.
Ben Shneiderman (links) met Catherine Plaisant op Webshop 2012. Shneiderman beschreef de sprongzoektocht in 1978.

Probeer het zelf

Open de app, kies een waarde bij Zoek naar en druk op Stap. Elke sprong markeert de laatste waarde van een blok; overgeslagen blokken vervagen, en het blok waar het doel in kan staan is gearceerd terwijl het wordt doorlopen. Zet bij 40 staven Spronggrootte van √n op 2 of 8 en zie hoe de balans tussen springen en doorlopen verschuift.

Veelgestelde vragen

Wat is de tijdcomplexiteit van sprongzoeken?

O(√n) bij blokken van √n waarden: hoogstens ongeveer 2√n vergelijkingen. Het heeft O(1) extra geheugen nodig en een gesorteerde lijst.

Wat is het verschil tussen sprongzoeken en binair zoeken?

Binair zoeken halveert telkens het resterende deel en heeft ongeveer log₂ n vergelijkingen nodig, maar gaat heen en weer. Sprongzoeken springt vooruit in vaste stappen en doorloopt één blok, heeft ongeveer 2√n vergelijkingen nodig en stapt maar één keer terug.

Kan het laatste blok ook met binair zoeken worden doorzocht?

Ja. Het blok binair doorzoeken brengt het doorlopen terug van m vergelijkingen naar ongeveer log₂ m. De sprongen kosten nog steeds n/m, dus dan lonen grotere blokken.

Heeft sprongzoeken een gesorteerde lijst nodig?

Ja. Een blok overslaan is alleen veilig omdat een kleinere laatste waarde betekent dat elke waarde erin kleiner is. De app sorteert een ongesorteerde lijst eerst.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer sprongzoeken