Interpolation Search Algorithm in Java

Introduction

Hi Everyone,

In this Article, we will learn about the working of Interpolation Search. Interpolation Search is an advanced searching algorithm that improves upon binary search for uniformly distributed, sorted arrays. While binary search always divides the search space in half, interpolation search makes intelligent guesses about where the target element might be located based on the value being searched.

Syntax

pos = low + ((target - arr[low]) / (arr[high] - arr[low])) * (high - low);

This Syntax assumes that the elements are uniformly distributed. The position calculation is based on the proportion of where the target value falls within the range of values between the current low and high indexes.

Steps

1. Calculate the probable position using the interpolation formula
2. If the element at the calculated position matches the target, return the position
3. If the target is smaller than the element at the calculated position, search the left subarray
4. If the target is larger, search the right subarray
5. Repeat until the element is found or the search space is exhausted

Code Example

package com.loki.dsa.sorting.blog;
import java.util.Arrays;
public class InterpolationSearch {

    public static int interpolationSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        // Continue searching while the target is within the range
        while (low <= high && target >= arr[low] && target <= arr[high]) {
            // If there's only one element left
            if (low == high) {
                return arr[low] == target ? low : -1;
            }
            // Calculate the probable position using interpolation formula
            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
            // Ensure pos is within bounds (safety check)
            if (pos < low || pos > high) {
                break;
            }
            // If element found at calculated position
            if (arr[pos] == target) {
                return pos;
            }
            // If target is smaller, search left subarray
            if (arr[pos] > target) {
                high = pos - 1;
            } else {
                // If target is larger, search right subarray
                low = pos + 1;
            }
        }
        return -1; // Element not found
    }
    /**
     * Recursive implementation of interpolation search
     */
    public static int interpolationSearchRecursive(int[] arr, int low, int high, int target) {
        // Base cases
        if (low > high || target < arr[low] || target > arr[high]) {
            return -1;
        }
        if (low == high) {
            return arr[low] == target ? low : -1;
        }
        // Calculate probable position
        int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        // Safety check for position bounds
        if (pos < low || pos > high) {
            return -1;
        }
        // If element found
        if (arr[pos] == target) {
            return pos;
        }
        // Recursive calls for subarrays
        if (arr[pos] > target) {
            return interpolationSearchRecursive(arr, low, pos - 1, target);
        } else {
            return interpolationSearchRecursive(arr, pos + 1, high, target);
        }
    }
    public static void main(String[] args) {
        // Test with uniformly distributed array
        int[] uniformArray = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        System.out.println("Array: " + Arrays.toString(uniformArray));
        int target = 70;
        int result = interpolationSearch(uniformArray, target);
        if (result != -1) {
            System.out.println("Element " + target + " found at index " + result);
        } else {
            System.out.println("Element " + target + " not found");
        }
        // Test with non-uniform array
        int[] nonUniformArray = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
        System.out.println("\nNon-uniform array: " + Arrays.toString(nonUniformArray));
        target = 64;
        result = interpolationSearch(nonUniformArray, target);
        if (result != -1) {
            System.out.println("Element " + target + " found at index " + result);
        } else {
            System.out.println("Element " + target + " not found");
        }
        // Test recursive implementation
        target = 32;
        result = interpolationSearchRecursive(nonUniformArray, 0, nonUniformArray.length - 1, target);
        System.out.println("Recursive search for " + target + ": " +
                (result != -1 ? "found at index " + result : "not found"));
    }
}

Output

Time and Space Complexity

Time Complexity

• Best Case: O(1) when the element is found at the first calculated position.
• Average Case: O(log log n) for uniformly distributed data.
• Worst Case: O(n) when data is not uniformly distributed or when searching for elements at the extremes.

Space Complexity

• Iterative version: O(1)
• Recursive version: O(log log n) due to recursion stack.

When to Use Interpolation Search?

Most effective when,

• The array is sorted and uniformly distributed.
• You're dealing with numerical data.
• The dataset is large.
• You need better than O(log n) performance on average.

Less effective when,

• Data is not uniformly distributed.
• Working with small datasets.
• The overhead of position calculation outweighs the benefits.

Comparison with Binary Search

Aspect	Binary Search	Interpolation Search
Time Complexity (Average)	O(log n)	O(log log n)
Time Complexity (Worst)	O(log n)	O(n)
Data Distribution Dependency	No	Yes
Implementation Complexity	Simple	Moderate

Summary

Interpolation search is a powerful algorithm that can significantly outperform binary search under the right conditions. Its ability to achieve O(log log n) average time complexity makes it valuable for searching large, uniformly distributed datasets. However its performance dependency on data distribution means it should be chosen carefully based on your specific use case.