Interpolation Search

Interpolation search works by estimating the position of the target value within the list based on its value relative to the minimum and maximum values in the list. This estimation allows the algorithm to shrink the search space more efficiently than binary search, which always divides the search space in half.

How it works

The basic idea of interpolation search is to use the target value and the range of values in the list to calculate a probable position for the target value, similar to how one looks for a specific page number in a sorted book. If the calculated position matches the target value, the search is successful and the index of the target value is returned. If the calculated position is less than the target value, the search continues in the right-hand secondary array. If the calculated position is greater than the target value, the search continues in the left secondary matrix. If the target value is not in the list, the algorithm returns a value indicating that the item was not found.

public static int InterpolationSearch(int[] array, int target)
{
    var left = 0;
    var right = array.Length - 1;

    while (left <= right && target >= array[left] && target <= array[right])
    {
        if (left == right)
        {
            return array[left] == target ? left : -1;
        }

        var position = left + ((target - array[left]) * (right - left)) / (array[right] - array[left]);
        if (array[position] == target)
        {
            return position;
        }

        if (array[position] < target)
        {
            left = position + 1;
        }
        else
        {
            right = position - 1;
        }
    }

    return -1;
}

Time complexity

The time complexity depends on the distribution of values in the list. In the best case, when the target value is at the estimated position, the time complexity is O(1). For uniformly distributed data, the average time complexity is O(log log n), where n is the number of elements in the list. In the worst-case scenario, the time complexity may degrade to O(n), which is slower than binary search.

Space complexity

The space complexity is O(1) because the algorithm requires only a constant amount of additional memory to store the left, right, and position indexes during the search process. This minimal space overhead makes interpolation search suitable for applications with limited memory resources or when space efficiency is a priority.

Conclusion

Interpolation search stands out as a potent search algorithm, offering accelerated search times for large, uniformly distributed datasets.

Its relative ease of understanding and implementation, along with minimal additional memory requirement during the search process, adds to its appeal. However, it's important to note that it functions exclusively on ordered numeric lists, and its performance may notably decline for unevenly distributed data. Moreover, for very small data sets, the performance improvement might not be significant.

Regardless of these constraints, when applied to large, uniformly distributed numerical sets, interpolation search can deliver significant performance enhancements over traditional binary search, marking it as a highly efficient choice for these specific scenarios.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)