Interactive DSA and system design

Learn complex engineering ideas by watching them move.

6stepsO(log log n)averageO(1)space

Searching lab

Interpolation Search Probe Flow

Step 1 / 6

low

high

Comparing Pivot / Mid Swapping Sorted / Found Active Range

Animation speed

Space play / pause←→ stepR reset

Current operation

Start

Interpolation Search begins on the sorted array. Target value is 36. Unlike binary search, the probe position is estimated using value distribution.

Algorithm state

36Target0Low9High

Try your own input

Use 3-12 positive numbers separated by commas.

Complexity notes

O(log log n)averageO(n)worstO(1)spaceN/Astable

Synced code trace

function interpolationSearch(arr, target) {  let low = 0, high = arr.length - 1;  while (low <= high && target >= arr[low] && target <= arr[high]) {    const pos = low + Math.floor(      ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])    );    if (arr[pos] === target) return pos;    else if (arr[pos] < target) low = pos + 1;    else high = pos - 1;  }  return -1;}

Interactive Notes

✓ Notes are saved automatically and persist per step.