Interpolation Search

Interpolation Search Interpolation Search is an improved variant of Binary Search. While Binary Search always checks the middle of the current range, Interpolation Search estimates the probable position of the target value based on the distribution of the data. It is especially efficient for uniformly distributed sorted arrays, offering better performance than Binary Search in such cases.

---

Interpolation Search Logic

The core idea behind Interpolation Search is similar to how humans search for names in a phone book. If you're looking for "Smith," you don’t start at the middle—you jump closer to where "Smith" is likely to appear.

Here's the step-by-step logic:

1. The array must be sorted in ascending order.

2. Start with two pointers:

   • low = 0 (start index)

   • high = n - 1 (end index)

3. Calculate the estimated position using the formula:

   pos=low+((target−arr[low])×(high−low)arr[high]−arr[low])\text{pos} = \text{low} + \left( \frac{(target - arr[low]) \times (high - low)}{arr[high] - arr[low]} \right)

4. Compare arr[pos] with the target:

   • If arr[pos] == target, return pos.

   • If arr[pos] < target, search the upper sub-array (low = pos + 1).

   • If arr[pos] > target, search the lower sub-array (high = pos - 1).

5. Repeat steps 3–4 until the element is found or low > high.

---

Interpolation Search in Java

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;

        while (low <= high && target >= arr[low] && target <= arr[high]) {
            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

            if (arr[pos] == target)
                return pos;
            else if (arr[pos] < target)
                low = pos + 1;
            else
                high = pos - 1;
        }

        return -1;  // Element not found
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70};
        int target = 40;
        int result = interpolationSearch(arr, target);

        if (result != -1)
            System.out.println("Element " + target + " found at index " + result + ".");
        else
            System.out.println("Element " + target + " not found in the array.");
    }
}

---

Interpolation Search in C

#include <stdio.h>

int interpolationSearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

        if (arr[pos] == target)
            return pos;
        else if (arr[pos] < target)
            low = pos + 1;
        else
            high = pos - 1;
    }

    return -1;  // Element not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 40;

    int result = interpolationSearch(arr, size, target);

    if (result != -1)
        printf("Element %d found at index %d.\n", target, result);
    else
        printf("Element %d not found in the array.\n", target);

    return 0;
}

---

Time Complexity Analysis

Let n be the number of elements in the array.

Scenario	Time Complexity
Best Case	O(1)
Average Case	O(log log n)
Worst Case	O(n)

• Best case: When the estimated position directly hits the target.

• Average case: When data is uniformly distributed.

• Worst case: When data is not uniformly distributed or when elements are clustered at the edges.

---

Space Complexity

• O(1) – No additional memory is required beyond a few integer variables.

---

Requirements and Limitations

Aspect	Details
Data type	Must be numeric and sorted in ascending order
Distribution	Works best on uniformly distributed data
Not suitable for	Highly skewed or irregular distributions
Overflow possibility	Formula can cause overflow if not handled properly

---

Summary

Feature	Interpolation Search
Input Requirement	Sorted & uniformly distributed
Best Time	O(1)
Average Time	O(log log n)
Worst Time	O(n)
Space	O(1)
Suitable For	Large datasets with predictable distributions
Advantage Over Binary Search	Faster for uniformly distributed data

Interpolation Search combines the structure of Binary Search with an estimation technique to make smarter guesses about element positions. While not universally applicable, it excels in niche cases where data is numeric, sorted, and uniformly spaced.