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

// 原始代码片段
// int[] array = new int[args.length];
// int wantedValue = Integer.parseInt(args[0]);
// for(int i = 1; i < args.length; i++) {
//    array[i] = Integer.parseInt(args[i]);
// }

// 修正后的代码片段
int[] array = new int[args.length - 1]; // 数组大小应为命令行参数总数减去一个（wantedValue）
int wantedValue = Integer.parseInt(args[0]);
for (int i = 1; i < args.length; i++) {
    array[i - 1] = Integer.parseInt(args[i]); // 从array[0]开始填充
}

// 原始代码片段
// int leftBoundary = 1;

// 修正后的代码片段
int leftBoundary = 0; // 数组索引从0开始

// 原始split方法片段
// private static int split(int[] haystack, int needle, int left, int right) {
//     if(haystack[right] == haystack[left]) {
//         return left;
//     }else {
//         needle = left + ((needle - haystack[left]) / (haystack[right] - haystack[left])) * (right - left);
//         return needle;
//     }
// }

// 修正后的split方法片段
private static int split(int[] haystack, int needle, int left, int right) {
    // 处理边界情况：如果左右边界值相同，则直接返回左边界
    // 避免除以零错误，并处理所有元素相同的情况
    if (haystack[right] == haystack[left]) {
        return left;
    } else {
        // 关键修正：将分子强制转换为double类型，确保执行浮点除法
        return (int) (left + ((double) (needle - haystack[left]) / (haystack[right] - haystack[left])) * (right - left));
    }
}

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，且haystack非空

        // 如果左右边界值相同，则目标值可能就在left（或right），
        // 或者目标值不在数组中，但这是最接近的索引。
        // 同时也避免了后续除以零的错误。
        if (haystack[right] == haystack[left]) {
            return left;
        } else {
            // 插值查找核心公式
            // 关键点：将 (needle - haystack[left]) 强制转换为 double 类型，
            // 确保执行浮点除法，避免整数除法截断问题。
            return (int) (left + ((double) (needle - haystack[left]) / (haystack[right] - haystack[left])) * (right - left));
        }
    }

    // 完整的插值查找算法通常会包含一个循环，不断调用split方法缩小搜索范围
    // 这里仅展示split方法的正确实现，完整的search方法需要进一步实现
    private static int search(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]) {
                if (haystack[left] == needle) {
                    return left;
                } else {
                    return -1; // 未找到
                }
            }

            int pos = split(haystack, needle, left, right);

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

    public static void main(String[] args) {
        // 检查命令行参数数量
        if (args.length < 2) {
            System.out.println("Usage: java Search <wantedValue> <array_element1> <array_element2> ...");
            return;
        }

        // 1. 解析wantedValue和构建数组
        int wantedValue = Integer.parseInt(args[0]);
        int[] array = new int[args.length - 1]; // 数组大小为args.length - 1
        for (int i = 1; i < args.length; i++) {
            array[i - 1] = Integer.parseInt(args[i]); // 从array[0]开始填充
        }

        // 2. 初始化搜索边界
        int leftBoundary = 0; // 左边界应为0
        int rightBoundary = array.length - 1;

        // 3. 调用split方法（或完整的search方法）
        // 这里仅为了演示split方法的输出，通常会调用完整的search方法
        if (array.length == 0) {
            System.out.println("Array is empty.");
            return;
        }

        // 确保数组有序，插值查找要求数组必须是有序的
        // 实际应用中可能需要先排序或验证数组已排序
        // Arrays.sort(array); 

        // 演示split方法的输出
        int splitAtIndex = split(array, wantedValue, leftBoundary, rightBoundary);
        System.out.println("Initial estimated index by split method: " + splitAtIndex);

        // 演示完整的search方法的输出
        int foundIndex = search(array, wantedValue);
        if (foundIndex != -1) {
            System.out.println("Value " + wantedValue + " found at index: " + foundIndex);
        } else {
            System.out.println("Value " + wantedValue + " not found in the array.");
        }
    }
}