Как написать интерполяционный поиск рекурсивно? - 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 элементов и более) выдается исключение StackOverflowException.

В чем проблема?

Answer 1

Кажется, вы никогда не выходите из функции, вот еще один пример того, как этого добиться, и это работает для меня:

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

Answer 2

Я нашел решение. Это было только мое невнимание.

Просто пришлось поменять местами InterpolationSearch(arr, value, index + 1, right) и InterpolationSearch(arr, value, left, index - 1) функции.