Find the given key from the table by using interpolation search.

Drag the visited keys into the list below. Visited keys are the keys used as the value of probe.

Some addditional problems.

    int interpolationSearch(int[] table, int x)
    {
        int low = 0;
        int high = table.length-1;
        int mid;

        while(table[low] < x && table[high] >= x) {
	    // Division truncates 
	    mid = low + ((x-table[low]) * (high-low)) / (table[high] - table[low]); 

            if(table[mid] < x)
                low = mid + 1;
            else if(table[mid] > x)
                high = mid - 1;
            else
                return mid;
        }  

	if (table[low] == x)
	    return low;
	else
            return -1; // Not found
    }