插值查找算法
插值查找原理介绍:
1.插值查找算法类似与二分查找,不同的是插值查找每次从自适应mid处开始查找。
2.将折半查找中的求mid索引的公式,low表示左边索引,high表示右边索引,key就是前面我们讲的findValue。
mid = ( low + high ) / 2 = low + 1/2 * ( high - low ) 改成 mid = low + ( key - a[low] / a[high] - a[low] ) * ( high - low )
3.int mid = low + ( high - low ) * (key - a[low]) / (a[high] - a[low]) ;//插值索引
对应前面的代码公式:
int mid = left + (right - left) * (findVal - arr[left])/(arr[right]-arr[left]);
4.举例说明插值查找算法1-100的数组
数组 arr = {1,2,3,4,.....,100}
加入我们需要查找的值是1
int mid = 0 + (99 - 0) * (1 - 1 / 100 - 1) = 0 + 99 * 0 / 99 = 0
