DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

Back to Searching

Interpolation Search Visualizer

Watch how Interpolation Search estimates the position using linear interpolation, ideal for uniformly distributed data.

Time: O(log log n)

Space: O(1)

Requirement: Sorted & Uniform

Linear Interpolation

Target Value: 18

Search Range: [0, 14] | Comparisons: 0

Animation Speed: Normal

Target: 18 | Step: 1 of 0

Current Step:

Click Start to begin Interpolation Search visualization

Interpolation Search

Time Complexity:O(log log n)

Space Complexity:O(1)

Worst Case:O(n)

Best For:Uniform Data

Color Legend

Interpolated Position

Search Boundaries (L, R)

Target Found

Active Search Space

Eliminated Space

Interpolation Formula

pos = left + [(target - arr[left]) × (right - left)] / (arr[right] - arr[left])

This formula estimates where the target should be based on its value relative to the range.

Works best when data is uniformly distributed.

How It Works

1Calculate interpolated position
2Check element at calculated position
3Adjust search range based on comparison
4Repeat until found or exhausted

Python Implementation

def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while (left <= right and target >= arr[left] and target <= arr[right]):
        # If we have a single element
        if left == right:
            if arr[left] == target:
                return left
            else:
                return -1
        
        # Interpolation formula
        pos = left + int(((target - arr[left]) * (right - left)) / (arr[right] - arr[left]))
        
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

Real-world Applications

• Searching in phone directories
• Database indexing for numeric ranges
• Time-series data analysis
• Geographic coordinate searching
• Uniformly distributed scientific data
• Dictionary/glossary lookups

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

Back to Searching

Interpolation Search Visualizer

Watch how Interpolation Search estimates the position using linear interpolation, ideal for uniformly distributed data.

Time: O(log log n)

Space: O(1)

Requirement: Sorted & Uniform

Linear Interpolation

Target Value: 18

Search Range: [0, 14] | Comparisons: 0

Animation Speed: Normal

Target: 18 | Step: 1 of 0

Current Step:

Click Start to begin Interpolation Search visualization

Interpolation Search

Time Complexity:O(log log n)

Space Complexity:O(1)

Worst Case:O(n)

Best For:Uniform Data

Color Legend

Interpolated Position

Search Boundaries (L, R)

Target Found

Active Search Space

Eliminated Space

Interpolation Formula

pos = left + [(target - arr[left]) × (right - left)] / (arr[right] - arr[left])

This formula estimates where the target should be based on its value relative to the range.

Works best when data is uniformly distributed.

How It Works

1Calculate interpolated position
2Check element at calculated position
3Adjust search range based on comparison
4Repeat until found or exhausted

Python Implementation

def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while (left <= right and target >= arr[left] and target <= arr[right]):
        # If we have a single element
        if left == right:
            if arr[left] == target:
                return left
            else:
                return -1
        
        # Interpolation formula
        pos = left + int(((target - arr[left]) * (right - left)) / (arr[right] - arr[left]))
        
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

Real-world Applications

• Searching in phone directories
• Database indexing for numeric ranges
• Time-series data analysis
• Geographic coordinate searching
• Uniformly distributed scientific data
• Dictionary/glossary lookups