template <typename T>
int interpolation_search (T * arr, int size, T key)
{

    if ( size < 0 || ! arr )         // not the best way to handle this case, but it
         return -1 ;                 // serves to draw attention to it possibly happening.


    unsigned long long low = 0 ;
    unsigned long long high = size - 1 ;
    unsigned long long mid ;


    while ( ! (arr [high] == arr [low] || key < arr [low] || arr [high] < key)  )
    {
            mid = low + (key - arr [low]) * ((high - low) / ( arr [high] - arr [low])) ;

            if ( arr [mid] < key )
                 low = mid + 1 ;

            else if ( key < arr [mid] )
                      high = mid - 1 ;

            else return mid ;
    }

    if ( key == arr [low] )
         return low ;

    else return -1 ;

}