如何递归地编写插值搜索？ - C＃

Question

我需要编写一个递归函数，使用插值法在数组中查找元素。最好是基于递归。

这是我的代码：

static int? InterpolationSearch(int[] arr, int value, int left, int right)
{
    if (arr[left] == value) return left;
    else if (left == right || arr[left] == arr[right]) return null;

    int index = left + (value - arr[left]) * (right - left) / (arr[right] - arr[left]);

    if (arr[index] == value) return index;
    else if (arr[left] < value) return InterpolationSearch(arr, value, index + 1, right);
    else return InterpolationSearch(arr, value, left, index - 1);
}

在大数组（大约 1000 个元素或更多）中搜索时，它会抛出 WhosebugException。

有什么问题？

Answer 1

我找到了解决方案。是我一不留神。

只需交换 InterpolationSearch(arr, value, index + 1, right) 和 InterpolationSearch(arr, value, left, index - 1) 函数。

Answer 2

似乎你永远不会退出该功能，这是另一个如何实现这一点的例子，它对我有用：

public static int InterpolationSearch(int[] array, int value)
{
    int low = 0;
    int high = array.Length - 1;
    return InterpolationSearch(array, value, ref low, ref high);
}

private static int InterpolationSearch(int[] array, int value, ref int low, ref int high)
{
    int index = -1;

    if (low <= high)
    {
        index = (int)(low + (((int)(high - low) / (array[high] - array[low])) * (value - array[low])));
        if (array[index] == value) 
        {
            return index;
        }
        else
        {
            if (array[index] < value)
                low = index + 1;
            else
                high = index - 1;
        } 

        return InterpolationSearch(array, value, ref low, ref high);
    }

    return index;
}

如何递归地编写插值搜索？ - C＃

How to write interpolation search recursively? - C#

c#

arrays

recursion

search

interpolation