Search Algorithms: Linear vs Binary vs Jump vs Interpolation

Algorithm

Array

Array size 48

Playback

Speed 6 steps/s

Live Readout

Press Play or Step to begin.

Comparisons

Search space

Worst-case bound for this size

O(n) = 48

How it works

All four algorithms search a sorted array of n unique values for a target. They differ only in how they pick the next index to probe, which changes how fast the remaining search space shrinks:

Linear:        probe i = 0,1,2,...        worst case: n comparisons
Binary:        probe mid = lo + floor((hi-lo)/2)
               halves the range each step: worst case O(log2 n)
Jump:          probe every floor(sqrt(n))-th index,
               then scan linearly inside the found block: O(sqrt n)
Interpolation: probe pos = lo + floor((target-arr[lo])*(hi-lo)
                                        / (arr[hi]-arr[lo]))
               a linear guess of where target should sit if the
               data is uniformly spaced: average O(log log n),
               worst case still O(n) on skewed data

Binary search only needs the array to be sorted; it throws away half the remaining range on every comparison regardless of the value distribution.
Interpolation search uses the actual values (not just order) to jump straight toward where the target is likely to be — on a roughly uniform distribution this beats binary search, but on a heavily skewed distribution its guess can be far off and it degrades toward linear search. Switch the array to "Skewed" and compare its comparison count against Binary's to see this live.
Jump search trades some of binary search's speed for simplicity: it only ever moves forward in blocks of size ⌊√n⌋, then scans that block linearly — useful when backward jumps are expensive (e.g. searching on tape or slow external storage).

Real-world relevance: binary search underlies lookups in sorted indexes and B-trees; interpolation search is used in database range scans on numeric keys; jump search shows up in low-memory or sequential-access storage systems.

Unvisited Checked / eliminated Currently probing Found

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.