插值查找（Interpolation Search）是一种用于在有序数组中进行查找的高效算法，特别适用于具有均匀分布数据的大型数组。与二分查找不同，插值查找试图根据目标值的位置估计其在数组中的位置，以便更快地缩小查找范围。
- 迭代实现插值查找：
public static int interpolationSearchIterative(int[] array, int target) { int low = 0; int high = array.length - 1; while (low <= high && target >= array[low] && target <= array[high]) { int pos = low + ((target - array[low]) * (high - low)) / (array[high] - array[low]); if (array[pos] == target) { return pos; } else if (array[pos] < target) { low = pos + 1; } else { high = pos - 1; } } return -1; // 如果未找到目标元素，返回-1 }
- 递归实现插值查找：
public static int interpolationSearchRecursive(int[] array, int target, int low, int high) { if (low <= high && target >= array[low] && target <= array[high]) { int pos = low + ((target - array[low]) * (high - low)) / (array[high] - array[low]); if (array[pos] == target) { return pos; } else if (array[pos] < target) { return interpolationSearchRecursive(array, target, pos + 1, high); } else { return interpolationSearchRecursive(array, target, low, pos - 1); } } return -1; // 如果未找到目标元素，返回-1 }
- 无论是递归还是迭代实现，插值查找都要求在有序数组中进行查找。与二分查找不同的是，插值查找尝试根据目标值的估计位置来选择下一个比较的位置，以便更快地缩小查找范围。如果目标元素存在于数组中，则返回其索引位置；如果目标元素不存在于数组中，则返回-1。
