Інтерполяційний алгоритм пошуку

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;
}