Interpolated Binary Search

The interpolated binary search algorithm is a hybrid search algorithm that combines the strategies of binary search and interpolation to search through ordered data. It exploits the ability of interpolation search to estimate the position of the target value for uniformly distributed data, while exploiting the consistent performance of binary search regardless of data distribution.

How it works

The algorithm starts by estimating the position of the target value by interpolation search. If the estimated position is close to the target value, the algorithm continues to use interpolation search for subsequent iterations. If the estimated position is far from the target value, the algorithm switches to binary search.

public static int InterpolatedBinarySearch(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 middle = (left + right) / 2;
        var position = left + ((target - array[left]) * (right - left)) / (array[right] - array[left]);

        if (Math.Abs(middle - position) <= 1)
        {
            if (array[position] == target)
            {
                return position;
            }

            if (array[middle] == target)
            {
                return middle;
            }

            return -1;
        }

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

    return -1;
}

Time complexity

The time complexity of the interpolated binary search algorithm depends on the data distribution. For uniformly distributed data, the algorithm performs similarly to interpolation search, with an average-case time complexity of O(log log n), where n is the number of elements in the list. For non-uniformly distributed data, the algorithm degrades to binary search, with a time complexity of O(log n).

Space complexity

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

Conclusion

Interpolated binary search is an innovative search algorithm that capitalizes on the strengths of both binary and interpolated search, offering a flexible and efficient solution for searching through ordered data.

This unique algorithm adapts its search strategy based on the distribution of the data, making it highly effective in various situations, from uniformly distributed data to non-uniformly distributed data. It provides faster search times for uniformly distributed data and requires minimal additional memory during the search process. However, it's worth noting that it comes with increased complexity compared to binary search or interpolated search individually, which could potentially make it more challenging for some developers to understand and implement. Another limitation is its dependency on sorted data, and it may not be efficient for small datasets.

Nonetheless, considering its ability to adapt and perform in diverse scenarios, interpolated binary search emerges as a versatile and efficient search solution for a variety of ordered data scenarios.

References

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