AlgoViz: Interactive Algorithm Visualization Tool

Interpolation Search

Category: Searching | Time: O(log log n) | Space: O(1)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Interpolation Search

An improvement over Binary Search for instances where the values in a sorted array are uniformly distributed. It estimates the position of the target value rather than always checking the middle.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function interpolationSearch(arr, x) {
    let n = arr.length;
    let lo = 0, hi = n - 1;
    while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
        if (lo == hi) {
            if (arr[lo] == x) return lo;
            return -1;
        }
        let pos = lo + Math.floor(((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));
        if (arr[pos] == x)
            return pos;
        if (arr[pos] < x)
            lo = pos + 1;
        else
            hi = pos - 1;
    }
    return -1;
}

Frequently Asked Questions

About Interpolation Search

What is Interpolation Search?

How does the position probing work?

What is the time complexity of Interpolation Search?

What is the main requirement for using Interpolation Search?

What is the space complexity?

Why is it called 'Interpolation' Search?

When would Binary Search be preferred over Interpolation Search?

Can it handle non-integer data types?

How does it compare to Jump Search?

Is it difficult to implement?

Where can I learn more?