/*
相比于二分法的折半，插值就相当于折插值数，而什么是折插值数，我们需要先了解一下它的公式：
    mid=left+(key-a[left])*(rigt-left)/(a[rigt]-a[left]) 

nums	1	16	24	35	47	59	62	73	88	99
序号	0	1	2	3	4	5	6	7	8	9

在猜目标key=59的时候，我们知道59相对来说是略微偏大的，所以但偏大多少用什么来度量呢，
在二分法的时候：mid =(left+right)/2
这里采用的是中间1/2来统一度量，但我们有时知道目标key 靠近右端（左端），此时应该再采用统一
度量有点吃力不讨好，这也是二分法的一个缺点，故由此引入了插值法，将递归的mid
值修改成：mid=left+(key-a[left])*(rigt-left)/(a[rigt]-a[left]) 

插值二分中的mid可以随着要查找的key而自动调整，而不是固定除以2
这样当该数列分布不均匀时，会有很大的优势
比如有以下单调增数列：
a1=1,a2=500,a3=700,a4=900,a5=901，a6=902,a7=904,a8=905,a9=906,a10=907,a11=908
假设我们要找的数字为200，即key=200
当我们用普通二分查找时，mid=(1+11)/2=6
而插值二分时，mid=1+(200-1)*(11-1)/907
                =3
不难看出来，普通二分的mid需要从6开始查找，而插值二分只需要从3开始，当数列很长时，
这一优势会更加明显
*/