Interpolation Search Visualizer

Target:

Speed:

SlowFast

Elements:

715

(10)

Pos (Estimated)

Boundaries

Target Value

Found

Out of Range

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(log log n) for uniformly distributed values; O(n) in worst case.

Space Complexity: O(1) - uses constant extra space.

Best Case: O(1) - target is at the calculated position.

Worst Case: O(n) - poor distribution or target not present.

Prerequisite: Array must be sorted in ascending order.

How it works: Estimates the position of the target using the values at the boundaries, then searches left or right accordingly.

When to use: Large, sorted, uniformly distributed datasets.

Implementation

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