algorithm - 插值搜索超出范围

Question

这是维基百科的一段 sample implementation of interpolation search :

public int interpolationSearch(int[] sortedArray, int toFind){
    // Returns index of toFind in sortedArray, or -1 if not found
    int low = 0;
    int high = sortedArray.length - 1;
    int mid;    
    while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
        mid = low +
            ((toFind - sortedArray[low]) * (high - low)) /
            (sortedArray[high] - sortedArray[low]);  //out of range is possible here

        if (sortedArray[mid] < toFind)
            low = mid + 1;
        else if (sortedArray[mid] > toFind)
            // Repetition of the comparison code is forced by syntax limitations.
            high = mid - 1;
        else
            return mid;
    }

    if (sortedArray[low] == toFind)
        return low;
    else
        return -1; // Not found
}

为什么那里可能超出范围？

编辑:添加了整个代码

Answer 1

如果发生整数溢出，则此处可能超出范围。为了克服这个问题，您可以使用 float/double 而不是 32 位整数。

看看这个， What's wrong with this Interpolation search implementation?