Vergelijkingen
Nog mogelijk
Nodig bij binair zoeken

  • Doel
  • Nog mogelijk
  • Vergeleken
  • Uitgesloten
  • Gevonden

Meer over exponentieel zoeken

Exponentieel zoeken

Exponentieel zoeken vindt een waarde in een gesorteerde lijst in twee fasen. Eerst kijkt het naar plek 1, 2, 4, 8, 16 enzovoort en verdubbelt elke keer, tot de waarde daar niet kleiner is dan het doel. Dan doorzoekt het het stuk tussen de laatste twee plekken binair. Kies de waarde om naar te zoeken en zie waarom een doel vooraan al na een paar vergelijkingen gevonden wordt. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om per stap te gaan. Sleep de stappenschuif om ergens naartoe te springen. De stippellijn markeert de waarde die je zoekt, en het gearceerde deel is waar die nog kan staan. Exponentieel zoeken heeft een gesorteerde lijst nodig, dus een ongesorteerde lijst wordt eerst gesorteerd. Kies de waarde, 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

  1. Kies de waarde om naar te zoeken, en hoeveel staven. Of typ je eigen getallen: exponentieel zoeken sorteert ze eerst.
  2. Druk op Afspelen, of gebruik Stap en Terug om per stap te gaan. Sleep de stappenschuif om naar elk punt in het zoeken te springen.
  3. Zoek naar een waarde vooraan en een achteraan, en vergelijk het aantal met Nodig bij binair zoeken.

Hoe exponentieel zoeken werkt

Kijk naar de waarde op plek 1. Is die kleiner dan het doel, kijk dan naar plek 2, dan 4, 8, 16, elke keer het dubbele. Zodra een waarde niet kleiner is, stop je: het doel kan alleen na de vorige bekeken plek en vóór deze liggen. Doorzoek dat stuk binair. Loopt het verdubbelen voorbij het eind van de lijst, zoek dan binair van de laatst bekeken plek tot het eind.

Snel vooraan, en geen lengte nodig

Om een doel op plek i te bereiken, kijkt het verdubbelen ongeveer log₂ i keer, en het gevonden stuk bevat minder dan i waarden, dus binair zoeken kost nog eens ongeveer log₂ i. Dat is ongeveer 2 log₂ i in totaal, en dat hangt af van waar het doel staat, niet van hoe lang de lijst is. Een doel vooraan wordt sneller gevonden dan met gewoon binair zoeken; een doel achteraan kost tot ongeveer twee keer zoveel. Omdat de lengte van de lijst nooit nodig is, werkt het ook op lijsten die te lang zijn om te meten of geen bekend eind hebben.

Veelgestelde vragen

Hoe werkt exponentieel zoeken?

In een gesorteerde lijst controleert het plek 1, 2, 4, 8 enzovoort tot de waarde daar niet kleiner is dan het doel. Dan kan het doel alleen tussen de laatste twee gecontroleerde plekken liggen, en binair zoeken in dat stuk vindt het.

Is exponentieel zoeken sneller dan binair zoeken?

Als het doel vooraan in de lijst staat, ja: een doel op plek i kost ongeveer 2 log₂ i vergelijkingen, hoe lang de lijst ook is. Staat het doel achteraan, dan is gewoon binair zoeken sneller, tot ongeveer een factor twee.

Waarvoor wordt het gebruikt?

Voor zoeken in lijsten met een onbekende of onbegrensde lengte, zoals een stream of een oneindige reeks, en voor het samenvoegen van gesorteerde runs, waar de volgende match meestal dichtbij ligt. De galloping-modus van Timsort gebruikt hetzelfde idee van verdubbelen.

Waarom heet het exponentieel?

Omdat de plekken die het controleert exponentieel groeien: 1, 2, 4, 8, 16, elk twee keer de vorige. Het heet ook verdubbelend zoeken of galloping search.

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