InterpolationSearch -TizzyT

// Variant of BinarySearch utilizing linear interpolation to narrow the location of the key instead of halving.

private static int InterpolationSearch(int[] arr, int value)
{
    if (arr.Length == 1) return 0;
    int B = 0, T = arr.Length - 1;
    int L = arr[B], H = arr[T];
    if (L == value) return 0;
    if (H == value) return T;
    if (value < L || value > H) return -1;
    while (T > B)
    {
        int idx = B + (int)((T - B) * ((float)(value - L) / (H - L)));
        int val = arr[idx];
        if (val > value) H = arr[T = idx - 1];
        else if (val < value) L = arr[B = idx + 1];
        else return idx;
    }
    return -1;
}