Exponentieel zoeken
Binair zoeken moet weten waar de lijst eindigt voordat het in het midden kan kijken. Exponentieel zoeken niet: het galoppeert vooruit met steeds grotere stappen tot het voorbij het doel schiet, en doorzoekt dan de laatste stap binair. Daardoor is het ideaal voor lijsten met een onbekende lengte, en snel voor waarden vooraan.
Het idee
Controleer de waarde op plek 1, dan 2, 4, 8, 16 enzovoort, elke plek twee keer de vorige. Zolang de waarde daar kleiner is dan het doel, moet het doel verderop liggen. De eerste keer dat een waarde niet kleiner is, zit het doel klem: het ligt na de vorige gecontroleerde plek en niet later dan deze. Dat stuk is gesorteerd, dus binair zoeken vindt het doel, of laat zien dat het ontbreekt.
Een voorbeeld
Zoek 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Op plek 1 staat 2, op plek 2 staat 5, op plek 4 staat 12, allemaal kleiner. Op plek 8 staat 56, en dat is groter, dus 23 kan alleen op plek 5 tot 7 staan. Binair zoeken controleert het midden daarvan, plek 6, en vindt 23: 5 vergelijkingen, waar gewoon binair zoeken er 3 nodig heeft. Zoek je in dezelfde lijst naar 12, dan stopt het op plek 4 na 3 vergelijkingen, één minder dan binair zoeken, en 2 wordt op plek 1 gevonden met één vergelijking.
Hoeveel vergelijkingen
Voor een doel op plek i stopt het verdubbelen na ongeveer log₂ i stappen, en het laat een stuk van minder dan i plekken over, dat binair zoeken in nog eens ongeveer log₂ i afdekt. Het zoeken kost dus ongeveer 2 log₂ i vergelijkingen, hoe lang de lijst ook is. Staat het doel vooraan, dan is dat beter dan binair zoeken, dat altijd ongeveer log₂ n kost. Staat het achteraan, dan kost exponentieel zoeken tot ongeveer twee keer zoveel. Bij 40 waarden komt de app gemiddeld op ongeveer 3 vergelijkingen voor de eerste vijf plekken en ongeveer 9 voor de laatste vijf, tegen ongeveer 4,6 bij binair zoeken.
Onbekende lengte, en galloping
Jon Bentley en Andrew Yao beschreven deze verdubbelstrategie in 1976 voor onbegrensd zoeken: een waarde vinden in een gesorteerde reeks zonder bekend eind, zoals een oneindige lijst of een stream die je alleen plek voor plek kunt opvragen. Hetzelfde idee versnelt samenvoegen. Als een van twee gesorteerde runs blijft winnen, schakelt Timsort over op galloping: het kijkt 1, 2, 4, 8 plekken vooruit in de andere run om te vinden waar de volgende waarde hoort, in plaats van plek voor plek te stappen.
Probeer het zelf
Open de app, kies een waarde bij Zoek naar, en druk op Stap. Elke blik op plek 1, 2, 4, 8 enzovoort wordt gemarkeerd; zodra een waarde niet kleiner is, wordt het stuk tussen de laatste twee plekken gearceerd en neemt binair zoeken het over. Zoek naar een kleine waarde en daarna naar een grote, en vergelijk het aantal met de tegel voor binair zoeken.
Veelgestelde vragen
Wat is de tijdcomplexiteit van exponentieel zoeken?
O(log i) voor een doel op plek i, dus hooguit O(log n) voor een lijst van n waarden. Het heeft O(1) extra geheugen en een gesorteerde lijst nodig.
Wat is het verschil tussen exponentieel zoeken en binair zoeken?
Binair zoeken begint met de hele lijst en heeft de lengte nodig. Exponentieel zoeken vindt eerst door verdubbelen een stuk waarin het doel zit, en doorzoekt dan alleen dat stuk binair. Het is sneller als het doel vooraan staat en werkt zonder de lengte te kennen.
Waarom de stap verdubbelen en niet een vast aantal optellen?
Een vaste stap optellen is jump search, dat ongeveer n gedeeld door de stap keer moet kijken om de lijst door te komen. Verdubbelen bereikt plek i na ongeveer log₂ i keer kijken, en het stuk dat overblijft is nooit meer dan twee keer te groot, dus het binair zoeken daarna blijft kort.
Waar wordt exponentieel zoeken gebruikt?
Bij zoeken in onbegrensde of heel lange gesorteerde data, bij het samenvoegen van gesorteerde runs (galloping in Timsort), en bij het vinden van de eerste plek waar een voorwaarde waar wordt als er geen bovengrens bekend is.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer exponentieel zoeken