Java插值查找算法实现详解与常见陷阱分析

// 假设args[0]是wantedValue，args[1]到args[args.length-1]是数组元素
int[] array = new int[args.length - 1]; // 数组大小应为args.length - 1
int wantedValue = Integer.parseInt(args[0]);

for (int i = 1; i < args.length; i++) {
    array[i - 1] = Integer.parseInt(args[i]); // 将args[i]填充到array[i-1]
}

int leftBoundary = 0; // 搜索应从数组的第一个元素（索引0）开始
int rightBoundary = array.length - 1; // 搜索到数组的最后一个元素

private static int split(int[] haystack, int needle, int left, int right) {
    // 避免除以零的错误：如果左右边界值相同，则目标值只能在左边界（或不存在）
    if (haystack[right] == haystack[left]) {
        return left; // 或者根据具体逻辑判断是否返回-1或进行其他处理
    } else {
        // 关键：将分子或分母强制转换为double，确保进行浮点数除法
        // needle在此处代表wantedValue
        return (int) (left + ((double) (needle - haystack[left]) / (haystack[right] - haystack[left])) * (right - left));
    }
}

import java.util.Arrays; // 引入Arrays用于打印数组，便于调试

public class Search {

    /**
     * 根据插值查找公式估算目标值可能所在的索引。
     * 该方法是插值查找算法的核心，用于计算下一个探查点。
     *
     * @param haystack 要搜索的有序数组。
     * @param needle   要查找的目标值。
     * @param left     当前搜索区间的左边界索引。
     * @param right    当前搜索区间的右边界索引。
     * @return 估算出的目标值索引。
     */
    private static int split(int[] haystack, int needle, int left, int right) {
        // 边界条件检查：确保left和right有效
        if (left > right || needle < haystack[left] || needle > haystack[right]) {
            // 如果目标值超出当前搜索区间，或者区间无效，则返回-1表示未找到
            // 注意：这只是split方法的一种处理方式，完整的search方法会更复杂
            return -1;
        }

        // 处理haystack[right] == haystack[left]的情况，避免除以零
        // 如果区间内所有值都相同，且目标值与这些值相等，则返回left
        if (haystack[right] == haystack[left]) {
            return (needle == haystack[left]) ? left : -1;
        }

        // 使用浮点数除法计算比例，然后转换为int索引
        // 公式：mid = left + (right - left) * ((needle - haystack[left]) / (haystack[right] - haystack[left]))
        return (int) (left + ((double) (needle - haystack[left]) / (haystack[right] - haystack[left])) * (right - left));
    }

    /**
     * 完整的插值查找算法。
     *
     * @param haystack 要搜索的有序数组。
     * @param needle   要查找的目标值。
     * @return 如果找到，返回目标值的索引；否则返回-1。
     */
    public static int interpolationSearch(int[] haystack, int needle) {
        int left = 0;
        int right = haystack.length - 1;

        while (left <= right && needle >= haystack[left] && needle <= haystack[right]) {
            // 如果数组只有一个元素或者左右边界值相同，则直接检查
            if (haystack[right] == haystack[left]) {
                return (needle == haystack[left]) ? left : -1;
            }

            // 计算估算索引
            int pos = split(haystack, needle, left, right);

            // 如果pos超出有效范围，或者split返回-1（表示不在当前区间），则未找到
            if (pos == -1 || pos < left || pos > right) {
                return -1;
            }

            if (haystack[pos] == needle) {
                return pos; // 找到目标值
            } else if (haystack[pos] < needle) {
                left = pos + 1; // 目标值在右侧
            } else {
                right = pos - 1; // 目标值在左侧
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        // 至少需要两个参数：wantedValue 和一个数组元素
        if (args.length < 2) {
            System.out.println("Usage: java Search <wantedValue> <array_element_1> <array_element_2> ...");
            return;
        }

        int wantedValue = Integer.parseInt(args[0]);
        int[] array = new int[args.length - 1];

        for (int i = 1; i < args.length; i++) {
            array[i - 1] = Integer.parseInt(args[i]);
        }

        // 重要的前提：插值查找要求数组必须是有序的
        // 在实际应用中，你可能需要先对数组进行排序，或者确保传入的数组已经排序
        // Arrays.sort(array); // 如果不确定数组有序，可以先排序

        System.out.println("Searching for: " + wantedValue);
        System.out.println("In array: " + Arrays.toString(array));

        // 调用 split 方法来演示其输出 (在实际查找中，split是interpolationSearch内部调用的)
        // int splitAtIndex = split(array, wantedValue, 0, array.length - 1);
        // System.out.println("Initial estimated index (from split method): " + splitAtIndex);

        int foundIndex = interpolationSearch(array, wantedValue);
        if (foundIndex != -1) {
            System.out.println("Found " + wantedValue + " at index: " + foundIndex);
        } else {
            System.out.println(wantedValue + " not found in the array.");
        }

        // 示例测试用例
        // java Search 4 1 2 3 4 5 6 -> Found 4 at index: 3
        // java Search 4 1 2 3 5 6 -> 4 not found in the array. (因为4不存在，但会返回-1)
        // java Search 0 1 2 3 4 5 6 -> 0 not found in the array.
        // java Search 7 1 2 3 4 5 6 -> 7 not found in the array.
    }
}