java - 我执行的插值搜索算法有什么问题？

Question

所以我在这里用 Java 实现了一个插值搜索算法:

public static boolean search(int key, int[] array) {
    int low = 0, high = array.length - 1;
    int middle = -1;

    while(low <= high) {
        middle = low + (((high - low) / (array[high] - array[low])) * (key - array[low]));
        if(array[middle] == key)
            return true;
        else {
            if(array[middle] < key)
                low = middle + 1;
            else
                high = middle - 1;
        }
    }
    return false;
}

它适用于数组范围内的值，始终返回 true，但对于我的数组范围外的值它不起作用(即，如果我有一个 1-15 的元素列表，则值 0 和 16 不会当我得到一个 ArrayIndexOutOfBoundsException 时工作。

我似乎无法从调试器中找出哪里出错了。

谢谢!

Answer 1

问题是 key变量用于计算 middle ，因此必须在循环之前对其进行验证，以检查它是否低于数组中的最低值并高于数组中的较高值:

while((array[high] != array[low] && key >= array[low] && key <= array[high]))

如果语句为假，则无需进入循环，因为您事先知道键不在数组内(因为数组已排序)。

检查 Wikipedia 上的实现