以下是使用Java实现插值查找算法的代码:
public class InterpolationSearch {
public static int interpolationSearch(int[] arr, int x) {
// 获取数组的长度
int n = arr.length;
// 初始化low和high指针
int low = 0;
int high = n - 1;
while (low <= high && x >= arr[low] && x <= arr[high]) {
// 如果数组中只有一个元素
if (low == high) {
if (arr[low] == x) {
return low;
}
return -1;
}
// 使用插值公式预测位置
int pos = low + ((high - low) / (arr[high] - arr[low])) * (x - arr[low]);
// 检查预测位置的元素
if (arr[pos] == x) {
return pos;
}
if (arr[pos] < x) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
int x = 18;
int result = interpolationSearch(arr, x);
if (result != -1) {
System.out.println("元素" + x + "在数组中的索引为" + result);
} else {
System.out.println("元素不在数组中");
}
}
}
这个示例程序中,interpolationSearch
方法接受一个有序数组和目标值,并返回目标值在数组中的索引位置。如果目标值不在数组中,则返回-1。