Interpolatiezoeken
Als je ‘Taylor’ opzoekt in een telefoonboek, sla je het niet in het midden open: je slaat het achterin open, omdat de T laat in het alfabet komt. Interpolatiezoeken doet hetzelfde met getallen. Het raadt waar het doel moet staan aan de hand van hoe groot het is, en bij gelijkmatig verdeelde data is die gok opvallend goed.
Het idee
Binair zoeken kijkt altijd in het midden, waar het ook naar zoekt. Interpolatiezoeken gebruikt de waarden. Loopt het overgebleven deel van de lijst van 10 tot 100 en is het doel 70, dan ligt het doel op twee derde van de eerste naar de laatste waarde, dus kijkt het op twee derde van de plekken. Als formule ligt de poging op lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Na de poging houdt het het deel aan de goede kant over, precies zoals binair zoeken, en schat het opnieuw.
Twee voorbeelden
In 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 kijkt een zoektocht naar 70 meteen op plek 7: gevonden in 1 poging, waar binair zoeken er 4 nodig heeft. Neem nu 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 en zoek 9. Door de 999 komt elke schatting bij het begin uit: het zoeken kijkt op 1, 2, 3 enzovoort, één plek per keer, en heeft 9 pogingen nodig waar binair zoeken er 3 nodig heeft.
Hoe snel het is
Als de waarden gelijkmatig verdeeld zijn, of willekeurig getrokken uit een gelijkmatige verdeling, verkleint elke poging het overgebleven deel van ongeveer n tot ongeveer √n. Dat geeft gemiddeld ongeveer log₂(log₂ n) pogingen: rond de 5, zelfs voor een miljard waarden, tegen 30 bij binair zoeken. Als de waarden heel ongelijkmatig verdeeld zijn, kan een poging maar één waarde weghalen, en is het slechtste geval n pogingen, even slecht als lineair zoeken. Elke poging kost ook een deling, dus in de praktijk loont het vooral als pogingen duur zijn, zoals bij lezen van schijf.
Geschiedenis en varianten
W. W. Peterson beschreef interpolatiezoeken in 1957, om records te vinden in opslag met willekeurige toegang. Het gemiddelde van log log n bij gelijkmatig verdeelde sleutels werd in 1978 bewezen door Perl, Itai en Avni. Praktische versies beschermen zich tegen slechte data door binaire stappen in te mengen, bijvoorbeeld interpolatie-sequentieel zoeken of interpolatie-binair zoeken, zodat het slechtste geval dicht bij log n blijft.
Probeer het zelf
Open de app, kies een waarde bij Zoek naar en druk op Stap. Elke poging vertelt hoe ver het doel tussen de twee eindwaarden ligt en naar welke plek dat wijst. Zet Verdeling op Gelijkmatig en de meeste zoektochten eindigen na één poging; zet hem op Scheef en de pogingen kruipen langs het begin van de lijst. De laatste tegel toont hoeveel stappen binair zoeken nodig zou hebben voor dezelfde waarde.
Veelgestelde vragen
Wat is de tijdcomplexiteit van interpolatiezoeken?
Gemiddeld O(log log n) bij gelijkmatig verdeelde waarden, en O(n) in het slechtste geval. Het heeft O(1) extra geheugen en een gesorteerde lijst nodig.
Wat is het verschil tussen interpolatiezoeken en binair zoeken?
Binair zoeken kijkt altijd in het midden van wat over is. Interpolatiezoeken kijkt waar het doel zou moeten staan, afgaande op de waarden aan beide uiteinden. Dat is veel beter bij gelijkmatig verdeelde waarden en kan veel slechter zijn bij scheve.
Welke data past bij interpolatiezoeken?
Gesorteerde numerieke sleutels die vrij gelijkmatig verdeeld zijn: opeenvolgende ID's met weinig gaten, tijdstempels van regelmatige gebeurtenissen, of gehashte sleutels. Het past bij data waar een poging duur is en wat rekenwerk goedkoop.
Waarom biedt de app verschillende verdelingen?
Omdat de verdeling bepaalt hoe goed de schattingen zijn. Gelijkmatige waarden laten interpolatiezoeken bijna magisch lijken, en scheve waarden tonen de zwakte. Ze vergelijken met het aantal bij binair zoeken is de duidelijkste manier om te zien wanneer je welke gebruikt.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer interpolatiezoeken