我实现插值搜索算法有什么问题？(What's wrong with my implementation of an interpolation search algorithm?)

我实现插值搜索算法有什么问题？(What's wrong with my implementation of an interpolation search algorithm?)

所以我在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 ）。

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

谢谢！

So I've got an implementation of an interpolation search algorithm in Java here:

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; }

It works for values within the array's range, always returning true, but for values outside my array's range it doesn't work (i.e. if i have a list of elements from 1-15, the values 0 and 16 won't work as I get an ArrayIndexOutOfBoundsException).

I can't seem to figure out from the debugger where i'm going wrong.

Thanks!

最满意答案

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

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

如果语句为false，则不需要进入循环内部，因为您事先知道密钥不在数组内（因为数组已排序）。

检查维基百科上的实现。

The problem is that the key variable is used for calculating the middle, thus it has to be validated before the loop to be checked if it's lower than the lowest value and higher than the higher value in the array:

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

If the statement is false, then there's no need to go inside the loop because you know a priori that the key is not inside the array (since the array is sorted).

Check the implementation on Wikipedia as well.