AlgoScope

Interpolation Search

Probe where a straight line through the range ends would put the target. Log log n on even data.

Searching, algorithm, intermediate
90 equals 90: found at index 8.active 0-1110020130240350460570680790810091101012011lowprobehigh90 = 90

Search Variants: Interpolation on even data

Decision, step 3 of 4

90 equals 90: found at index 8.

How search variants works

Cost

Best
O(1)
Average
O(log log n)
Worst
O(n)
Space
O(1)

Average case assumes uniformly distributed keys.

Taught by the same lesson

Search Variants covers these too, in the same run.