思路

插值查找算法是二分查找算法的升级版，即优化算法，如果要查找的数组中有大量的数据，而要查找的数是第一个或者最后一个，那么二分查找也要耗费一定的时间，原因在于对Mid值的确定每次都是在中间，为了解决这个问题，对二分查找进行优化。
插值查找思路与二分查找思路相同，但是插值查找在确定中间值midVal时使用自适应的算法，即让要查找的值对应的索引越发接近该索引对用在数组元素中的值，那么通过很少的次数就可以查找到该值。
被查找的得是有序数组。

公式

//这是插值查找取值的公式
int midindex = low+(high-low)*(findval-array[low])/(array[high]-array[low])

感觉就是求要查找的值在数组中的大概比例位置，好一次就接近这个值

数据值分布不均匀的情况下，插值查找不一定比二分查找快

代码
```csharp using System; using System.Collections.Generic;

namespace ConsoleApp1 { class Program { static void Main(string[] args) { int[] arr = new int[8] { 1, 2, 4, 6, 7, 8, 9, 13 }; Console.WriteLine(InsertValiueSearch(arr,0,7,2)); }

    static int InsertValiueSearch(int[] array,int low,int high,int findval)
    {
        //退出递归的条件之一，防止索引越界越界，判断值得合法性
        if (low > high || findval < array[0] || findval > array[high])
            return -1;
        //求出mid
        int midindex = low + (high - low) * (findval - array[low]) / (array[high] - array[low]);
        //midindex+-1是因为在这次比较里面midindex指针的值已经比较过了，不是要查找的值，所以下次查找界限就+-1
        if (findval > array[midindex])//说明应该向右边查找递归
            return InsertValiueSearch(array, midindex + 1, high, findval);
        else if (findval < array[midindex])//这里应该向左边查找递归
            return InsertValiueSearch(array, low, midindex - 1, findval);
        else
            return midindex;
    }
}

}

```

插值查找

思路

代码