TRAKLA2

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

Some additional 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
}

Drag the visited keys into the list below. Visited keys are the values of table[mid] during the search.