Pogingen
Nog mogelijk
Nodig bij binair zoeken

  • Doel
  • Nog mogelijk
  • Vergeleken
  • Uitgesloten
  • Gevonden

Meer over interpolatiezoeken

Interpolatiezoeken

Interpolatiezoeken zoekt een waarde in een gesorteerde lijst zoals je een telefoonboek openslaat: voor een naam met een T sla je het achterin open, niet in het midden. Het schat de plek van het doel uit de waarden aan beide uiteinden van het deel dat over is. Kies de waarde en hoe de waarden verdeeld zijn, loop stap voor stap door de pogingen, en zie wanneer de schatting binair zoeken verslaat en wanneer niet. 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 gestreepte lijn markeert de waarde die je zoekt, en het gearceerde deel is waar die nog kan staan. Interpolatiezoeken heeft een gesorteerde lijst nodig, dus een ongesorteerde lijst wordt eerst gesorteerd. Kies de waarde, hoe de waarden verdeeld zijn, 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, hoe de waarden verdeeld zijn en hoeveel staven. Of typ je eigen getallen: interpolatiezoeken 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. Zet Verdeling op Gelijkmatig, Willekeurige gaten of Scheef, en vergelijk Pogingen met Nodig bij binair zoeken.

Hoe interpolatiezoeken werkt

Kijk naar de eerste en laatste waarde van het deel van de gesorteerde lijst waar het doel nog kan staan. Ligt het doel bijvoorbeeld op 40% van de eerste naar de laatste waarde, kijk dan op de plek op 40% van de plekken. Is de waarde daar het doel, dan ben je klaar. Is ze kleiner, dan blijven alleen de plekken erna over; is ze groter, alleen de plekken ervoor. Schat opnieuw in wat over is. Is het doel kleiner dan de eerste waarde of groter dan de laatste, dan staat het er niet in.

Wanneer de schatting werkt

Als de waarden gelijkmatig verdeeld zijn, zoals 10, 20, 30 enzovoort, komt de eerste schatting op het doel uit of er heel dichtbij, en zijn er gemiddeld ongeveer log₂(log₂ n) pogingen nodig: rond de 5 voor een miljard waarden, tegen 30 bij binair zoeken. Als de waarden samenklonteren, zoals 1, 2, 3, 4, 1000, komen de schattingen steeds op de verkeerde plek uit en haalt elke poging misschien maar één waarde weg, dus in het slechtste geval zijn het n pogingen. Binair zoeken doet het nooit slechter dan ongeveer log₂ n.

Veelgestelde vragen

Hoe werkt interpolatiezoeken?

In een gesorteerde lijst schat het uit de eerste en laatste waarde van het overgebleven deel waar het doel moet staan, kijkt op die plek en houdt alleen het deel aan de goede kant over. Het is als binair zoeken, maar met een slimmere gok dan het midden.

Is interpolatiezoeken sneller dan binair zoeken?

Bij gelijkmatig verdeelde waarden wel: gemiddeld ongeveer log₂(log₂ n) pogingen in plaats van ongeveer log₂ n. Bij ongelijkmatig verdeelde waarden kan het veel trager zijn, tot n pogingen, terwijl binair zoeken nooit meer dan ongeveer log₂ n nodig heeft.

Waarom kan het traag zijn?

Omdat de schatting ervan uitgaat dat de waarden gelijkmatig oplopen. Zijn de meeste waarden klein en een paar enorm, dan komt de schatting voor een klein doel steeds weer bij het begin uit en haalt ze telkens maar een of twee waarden weg.

Waar wordt interpolatiezoeken gebruikt?

Waar sleutels bijna gelijkmatig verdeeld zijn en pogingen duur zijn, zoals bij het opzoeken van records op schijf op numeriek ID of hash. Veel systemen combineren het met binair zoeken om een goed slechtste geval te houden.

Worden mijn getallen ergens naartoe gestuurd?

Nee. Het zoeken gebeurt 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