Skip to content

interpolation Search

requirements : sorted array time : uniformly distributed -> O (log log n). worst case -> O(n). space : O(1)

Improved over binary when the data is uniformaly distributed

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

Iterative

int interpolationSearch(int arr[], int n, int x) 
{ 
    int lo = 0, hi = (n - 1); 

    while (lo <= hi && x >= arr[lo] && x <= arr[hi]) 
    { 
        if (lo == hi) 
        { 
            if (arr[lo] == x) return lo; 
            return -1; 
        } 

        int pos = lo + (((double)(hi - lo) / 
            (arr[hi] - arr[lo])) * (x - arr[lo])); 

        if (arr[pos] == x) 
            return pos; 

        if (arr[pos] < x) 
            lo = pos + 1; 

        else
            hi = pos - 1; 
    } 
    return -1; 
}

Reursive

int interpolationSearch(int arr[], int lo,  
                        int hi, int x) 
{ 
    int pos; 

    if ( lo <= hi && x >= arr[lo] && 
                     x <= arr[hi]) 
    {  

        pos = lo + (((double)( hi - lo ) / 
                         (arr[hi] - arr[lo])) *  
                               (x - arr[lo])); 

        if( arr[pos] == x ) 
            return pos; 

        if( arr[pos] < x ) 
            return interpolationSearch(arr, pos + 1, 
                                       hi, x); 

        if( arr[pos] > x ) 
            return interpolationSearch(arr, lo,  
                                       pos - 1, x); 
    } 
    return -1; 
}

Interpolation vs Binary

log(log(n)) comparisons -> uniformly distributed

In the worst case:

(for instance where the numerical values of the keys increase exponentially)

It can make up to O(n) comparisons.