插值查找算法
- 插值查找原理介绍:
插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找。
- 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right. key 就是前面我们讲的 findVal
- int mid = low + (high – low) * (key – arr[low]) / (arr[high] – arr[low]) ;/插值索引/
对应前面的代码公式:
int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
- 举例说明插值查找算法 1-100 的数组
插值查找应用案例:
请对一个有序数组进行插值查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示”没有这个数”。
代码实现:
Original: https://www.cnblogs.com/XugeA/p/16330294.html
Author: xugeA
Title: 查找算法-插值查找算法
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/604757/
转载文章受原作者版权保护。转载请注明原作者出处!