AntInLoop

Interpolation Search Algorithm Code Implementations

Complete Interpolation Search Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Interpolation Search Algorithm Guide ยท Launch Interactive Visualizer

C++ Implementation

// Interpolation Search Implementation in C++
#include <iostream>
#include <vector>

class InterpolationSearch {
public:
    static int interpolationSearch(const std::vector<int>& arr, int target) {
        int left = 0;
        int right = arr.size() - 1;
        
        while (left <= right && target >= arr[left] && target <= arr[right]) {
            if (left == right) {
                if (arr[left] == target) return left;
                return -1;
            }
            
            // Interpolation formula
            int pos = left + (((right - left) / (arr[right] - arr[left])) * (target - arr[left]));
            
            if (arr[pos] == target) {
                return pos;
            }
            
            if (arr[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        
        return -1;
    }
    
    // Interpolation Search with bounds checking
    static int interpolationSearchSafe(const std::vector<int>& arr, int target) {
        if (arr.empty()) return -1;
        
        int left = 0;
        int right = arr.size() - 1;
        
        while (left <= right && target >= arr[left] && target <= arr[right]) {
            if (left == right) {
                if (arr[left] == target) return left;
                return -1;
            }
            
            // Avoid division by zero
            if (arr[right] == arr[left]) {
                if (arr[left] == target) return left;
                return -1;
            }
            
            int pos = left + (((right - left) / (arr[right] - arr[left])) * (target - arr[left]));
            
            if (arr[pos] == target) {
                return pos;
            }
            
            if (arr[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        
        return -1;
    }
};

JAVA Implementation

// Interpolation Search Implementation in Java
public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right && target >= arr[left] && target <= arr[right]) {
            if (left == right) {
                if (arr[left] == target) return left;
                return -1;
            }
            
            // Interpolation formula
            int pos = left + (((right - left) / (arr[right] - arr[left])) * (target - arr[left]));
            
            if (arr[pos] == target) {
                return pos;
            }
            
            if (arr[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        
        return -1;
    }
    
    // Interpolation Search with bounds checking
    public static int interpolationSearchSafe(int[] arr, int target) {
        if (arr.length == 0) return -1;
        
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right && target >= arr[left] && target <= arr[right]) {
            if (left == right) {
                if (arr[left] == target) return left;
                return -1;
            }
            
            // Avoid division by zero
            if (arr[right] == arr[left]) {
                if (arr[left] == target) return left;
                return -1;
            }
            
            int pos = left + (((right - left) / (arr[right] - arr[left])) * (target - arr[left]));
            
            if (arr[pos] == target) {
                return pos;
            }
            
            if (arr[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        
        return -1;
    }
}

JAVASCRIPT Implementation

// Interpolation Search Implementation in JavaScript
function interpolationSearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right && target >= arr[left] && target <= arr[right]) {
    if (left === right) {
      if (arr[left] === target) return left;
      return -1;
    }
    
    // Interpolation formula
    const pos = left + Math.floor(((right - left) / (arr[right] - arr[left])) * (target - arr[left]));
    
    if (arr[pos] === target) {
      return pos;
    }
    
    if (arr[pos] < target) {
      left = pos + 1;
    } else {
      right = pos - 1;
    }
  }
  
  return -1;
}

// Interpolation Search with bounds checking
function interpolationSearchSafe(arr, target) {
  if (arr.length === 0) return -1;
  
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right && target >= arr[left] && target <= arr[right]) {
    if (left === right) {
      if (arr[left] === target) return left;
      return -1;
    }
    
    // Avoid division by zero
    if (arr[right] === arr[left]) {
      if (arr[left] === target) return left;
      return -1;
    }
    
    const pos = left + Math.floor(((right - left) / (arr[right] - arr[left])) * (target - arr[left]));
    
    if (arr[pos] === target) {
      return pos;
    }
    
    if (arr[pos] < target) {
      left = pos + 1;
    } else {
      right = pos - 1;
    }
  }
  
  return -1;
}

PYTHON Implementation

# Interpolation Search Implementation in Python
def interpolation_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right and target >= arr[left] and target <= arr[right]:
        if left == right:
            if arr[left] == target:
                return left
            return -1
        
        # Interpolation formula
        pos = left + int(((right - left) / (arr[right] - arr[left])) * (target - arr[left]))
        
        if arr[pos] == target:
            return pos
        
        if arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

# Interpolation Search with bounds checking
def interpolation_search_safe(arr, target):
    if len(arr) == 0:
        return -1
    
    left = 0
    right = len(arr) - 1
    
    while left <= right and target >= arr[left] and target <= arr[right]:
        if left == right:
            if arr[left] == target:
                return left
            return -1
        
        # Avoid division by zero
        if arr[right] == arr[left]:
            if arr[left] == target:
                return left
            return -1
        
        pos = left + int(((right - left) / (arr[right] - arr[left])) * (target - arr[left]))
        
        if arr[pos] == target:
            return pos
        
        if arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1