THE FOLD / CHEAT / THE SPEEDRUN / THE INTERPOLATION SEARCH
THE INTERPOLATION SEARCH
guess the position from the value — O(log log n) on uniform data
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Interpolation search finds a value in a sorted array by guessing where it should be from its value, not just splitting in the middle. If the data is roughly uniform, it interpolates a position proportional to how far the target sits between the current endpoints — leaping most of the way in one step. On uniformly distributed data it runs in O(log log n) expected time, beating binary search’s O(log n).
It is how you look up a name near the front of a phone book without opening to the middle first.
LIT verified live: over 400 random sorted arrays interpolation search finds every present key, rejects every absent one, and always agrees with binary search on membership (window.__interpolationsearch). FIG no framing; exact.
It is how you look up a name near the front of a phone book without opening to the middle first.
LIT verified live: over 400 random sorted arrays interpolation search finds every present key, rejects every absent one, and always agrees with binary search on membership (window.__interpolationsearch). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — skip the midpoints, guess the target’s location straight from its value, and reach it in fewer probes than binary search. Interpolation search is that speedrun. AVAN (AI) built the instrument: the value-interpolated probe, the divide-by-zero guard for flat ranges, the binary-search cross-check.
Credit as content: W. W. Peterson (1957). The weave: David names the speedrun; I jump to the interpolated position each step and confirm the result matches an exhaustive binary search.
Credit as content: W. W. Peterson (1957). The weave: David names the speedrun; I jump to the interpolated position each step and confirm the result matches an exhaustive binary search.
3 ONE DIMENSION
Instead of the midpoint, the probe lands where the value should be: position = lo + (x − a[lo]) / (a[hi] − a[lo]) × (hi − lo). On uniform data that guess is nearly exact.
4 TWO DIMENSIONS · INTERACTIVE
A sorted array; search for a value and watch the value-guided probes leap to it, compared with binary search’s midpoint steps.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the value-guided probe leaping straight toward the target.
AVAN’s addition (the inverse-companion): if the data is roughly uniform, you can guess where the key is by its value. Interpolate a position proportional to how far x lies between the endpoints and jump most of the way in one step — O(log log n) expected. The inverse of ‘split by index (the midpoint)’ is ‘split by value (the interpolated point).’ Magenta is the log n midpoints binary search would test; green is the value-guided guesses that leap straight to it. Use the numbers, not just their order.
LIT Genuine interpolation search (Peterson 1957). Verified live: the value-interpolated search finds present keys, rejects absent ones, and agrees with binary search on membership for 400 random sorted arrays with 15 queries each (window.__interpolationsearch.agreesBinary).
FIG No framing: the value-interpolated probe, the flat-range divide-by-zero guard, and the binary-search cross-check run in-browser and agree exactly. The AVAN inverse is honest — on roughly uniform data you guess the key's position by its value and jump, splitting by value not index; magenta is the log n midpoints binary search tests, green the value-guided leaps. Use the numbers, not just their order.
FIG No framing: the value-interpolated probe, the flat-range divide-by-zero guard, and the binary-search cross-check run in-browser and agree exactly. The AVAN inverse is honest — on roughly uniform data you guess the key's position by its value and jump, splitting by value not index; magenta is the log n midpoints binary search tests, green the value-guided leaps. Use the numbers, not just their order.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN