- Doel
- Actief blok
- Vergeleken
- Uitgesloten
- Gevonden
Sprongzoeken
Sprongzoeken zit tussen lineair en binair zoeken in. Het gaat door een gesorteerde lijst in sprongen van m plekken en controleert alleen de laatste waarde van elk blok, tot het een blok bereikt waarvan de laatste waarde niet kleiner is dan het doel. Dan doorloopt het dat blok vanaf het begin. Kies de waarde en de spronggrootte, en zie hoeveel vergelijkingen de sprongen en het doorlopen kosten. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om ergens naartoe te springen. De stippellijn markeert de waarde die je zoekt, en het gearceerde deel is het actieve blok. Sprongzoeken heeft een gesorteerde lijst nodig, dus een ongesorteerde lijst wordt eerst gesorteerd. Kies de waarde, de spronggrootte, hoeveel staven, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.
Hoe het werkt
- Kies de waarde om naar te zoeken, de spronggrootte en hoeveel staven. Of typ je eigen getallen: sprongzoeken sorteert ze eerst.
- Druk op Afspelen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om naar elk punt in het zoeken te springen.
- Probeer een spronggrootte van 2 en van 8 bij 40 staven, en vergelijk het aantal vergelijkingen met √n.
Zo werkt sprongzoeken
Verdeel de gesorteerde lijst in blokken van m waarden. Kijk naar de laatste waarde van het eerste blok. Is die kleiner dan het doel, dan kan het doel nergens in dat blok staan, dus spring naar het eind van het volgende blok en kijk opnieuw. Zodra de laatste waarde van een blok niet kleiner is, kan het doel alleen in dat blok staan: ga terug naar het begin ervan en controleer de waarden een voor een tot je het doel vindt of erlangs gaat.
De spronggrootte kiezen
Bij n waarden kosten de sprongen tot n/m vergelijkingen en het doorlopen tot m. Kleine sprongen maken het doorlopen kort maar de sprongen talrijk; grote sprongen doen het omgekeerde. Het totaal n/m + m is het kleinst bij m = √n, wat ongeveer 2√n vergelijkingen geeft: hoogstens 13 bij 40 waarden, tegen 40 bij lineair zoeken en 6 bij binair zoeken. Sprongzoeken gaat nooit meer dan één blok terug, wat helpt als achteruit door de data gaan traag is.
Veelgestelde vragen
Hoe werkt sprongzoeken?
In een gesorteerde lijst springt het vooruit in stappen van m plekken en controleert het de laatste waarde van elk blok. Zodra die waarde niet meer kleiner is dan het doel, kan het doel alleen in dat blok staan, dat het dan vanaf het begin doorloopt.
Wat is de beste spronggrootte?
√n, afgerond. De sprongen kosten tot n/m vergelijkingen en het doorlopen tot m, en hun som is het kleinst als die twee gelijk zijn, bij m = √n. Dat geeft in het slechtste geval ongeveer 2√n vergelijkingen.
Is sprongzoeken sneller dan binair zoeken?
Nee, binair zoeken heeft minder vergelijkingen nodig: ongeveer log₂ n tegen ongeveer 2√n. Sprongzoeken kan toch winnen als teruggaan door de data duur is, omdat het maar één keer terugstapt, naar het begin van één blok.
Welke treffer vindt het als waarden dubbel voorkomen?
De eerste. Elk overgeslagen blok eindigt met een waarde die kleiner is dan het doel, dus geen eerder blok kan een treffer bevatten, en het doorlopen begint aan het begin van het blok.
Worden mijn getallen ergens naartoe gestuurd?
Nee. Het zoeken draait in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor