Interpolation search - Algoritmy.net

Interpolation search - Algoritmy.net

The interpolation search is an improvement of the binary search for instances, where the values in the array are ordered and uniformly distributed.

The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element. Interpolation search calculates a position , where the value should be placed in accordance to the distribution of values a splits the array at . If the array contains numbers  and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found). The interpolation search calculates the probable position (index 9) and immediately finds the value. The expected complexity of the interpolation search in .

public static int interpolationSearch(int[] array, int value, int from, int to){

10.if(array[from] == value) return from;

11.else if(from == to || array[from] ==  array[to]) return -1; //not found

12. 

13.//probable position of the searched value

14.int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);

15. 

16.if(array[index] == value) return index;//found

17.//continue in the right part of the array

18.else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);

19.//continue in the left part of the array

20.else return interpolationSearch(array, value, from, index - 1);

21.}

http://www.geeksforgeeks.org/interpolation-search/

The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to middle element to check. On the other hand interpolation search may go to different locations according the value of key being searched. For example if the value of key is closer to the last element, interpolation search is likely to start search toward the end side.

To find the position to be searched, it uses following formula.

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

int interpolationSearch(int arr[], int n, int x)

{

    int lo = 0, hi = (n - 1);

    while (lo <= hi)

    {

        // Probing the position with keeping

        // uniform distribution in mind.

        int pos = lo + (((double)(hi-lo) /

              (arr[hi]-arr[lo]))*(x - arr[lo]));

 

        // Condition of target found

        if (arr[pos] == x)

            return pos;

 

        // If x is larger, x is in upper part

        if (arr[pos] < x)

            lo = pos + 1;

 

        // If x is smaller, x is in lower part

        else

            hi = pos - 1;

    }

    return -1;

}

Time Complexity : If elements are uniformly distributed, then O (log log n)). In worst case it can take upto O(n).
Auxiliary Space : O(1)

Read full article from Interpolation search - Algoritmy.net