Search Algorithm Growth Curves: Linear vs Binary vs Jump vs Interpolation

Distribution & Target

Growth chart

Max array size 65,536

Trials averaged per size 12

Current n on chart

–

Number-line spotlight

Spotlight array size 40

Press "Build chart" to measure real comparison counts, or "Probe next" to step one search live.

Spotlight comparisons

Spotlight bound

–

How it works

Instead of animating one search on a bar chart, this version measures all four algorithms directly: for each array size n it generates fresh sorted test arrays, runs every algorithm on real (present or deliberately absent) targets, counts actual comparisons, and plots the average against n on a log-x growth chart — so the O(n) / O(log n) / O(√n) / O(log log n) curves you see are computed, not illustrated.

Linear:        worst n, average ≈ n/2 (present)
Binary:        halves [lo,hi] each probe: worst = ⌊log2 n⌋ + 1
Jump:          block = ⌊√n⌋; worst ≈ 2·⌈√n⌉
Interpolation: pos = lo + (t−a[lo])·(hi−lo)/(a[hi]−a[lo])
               average ≈ O(log log n) on uniform keys,
               degrades toward O(n) when key values are
               spaced exponentially rather than uniformly

Uniform keys are spaced by a small near-constant gap — interpolation's linear guess is accurate and it beats binary search by a wide, measured margin as n grows.
Skewed here uses a genuinely adversarial construction: keys grow by a roughly constant ratio (exponential spacing) rather than a constant difference. This breaks interpolation's core assumption that value position tracks index position linearly, and its measured comparison count explodes toward linear search's — while binary search, which only ever compares order (never values), is completely unaffected.
Number-line spotlight plots one live array as dots positioned by their actual value (not by index), so a skewed array visibly clusters into a dense region with a long empty stretch — you can see directly why the value-based interpolation guess misfires there.

Note: an earlier 3D version of this simulator used a milder "skewed" generator (mostly small gaps with occasional random jumps) that, when measured here, did not actually make interpolation search worse than binary search on average — interpolation still won. This build's skewed generator was redesigned and numerically verified so the on-screen claim is actually true of the data it produces.

Unvisited Eliminated Probing Found