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