插值查找
引言
在介绍插值查找之前，首先考虑一个新问题，为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？ 若想从1 ~ 100 之间 100 个元素从小到大均匀分布的数组中查找1，使用二分查找我们要多次递归才能找到1， 我们自然会考虑从数组下标较小的开始查找，而不是折半。
插值查找基本思路
插值查找法，就是需要一个自适应的中间值。 由二分查找中mid索引的公式转变成； （key就是待查找的值）
对应代码公式： int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
代码
public static int insertValSearch(int[] arr
, int left
, int right
, int findVal
) {
if (left
> right
|| findVal
< arr
[0] || findVal
> arr
[right
]) {
return -1;
}
int mid
= left
+ (right
- left
) * (findVal
- arr
[left
]) / (arr
[right
] - arr
[left
]);
int midVal
= arr
[mid
];
if (findVal
< midVal
) {
return insertValSearch(arr
, left
, mid
- 1, findVal
);
} else if (findVal
> midVal
) {
return insertValSearch(arr
, mid
+ 1, right
, findVal
);
} else {
return mid
;
}
}
复杂度分析
查找成功或者失败的时间复杂度均为O(log2(log2n))。
注意
插值法未必比二分法效率高！！！ 对于表长较大的查找表，且查找表数据分布不均匀，此时插值法效率没有二分法效率高。
