Интерполяционный поиск, поиск по убыванию

Question

Я хочу изменить этот алгоритм, чтобы он мог находить значения в массиве, который был отсортирован в порядке убывания. В настоящее время это работает только по возрастанию.

public static int interpo(double[] array, double key, int order)
{
    int low = 0, high = array.Length - 1;
    int pos = 0;
    int count = 0;

    while ((low <= high) && (key >= array[low]) && (key <= array[high]))
    {
        count++;
        pos = Convert.ToInt32(low + (high - low) / (array[high] - array[low]) * 
            (key - array[low]));

        if (array[pos] == key)
        {
            // Write out the position and the value of whats in the position
            Console.WriteLine("\n     {0} : {1}", pos, array[pos]);                   
            break;
        }

        if (array[pos] < key)
            low = pos + 1;
        else
            high = pos - 1;

        // If the count is greater than the array size, do the following
        if (count > array.Length) 
        {
            // Pass through the position within the array to the close element 
            // method, which will display the closest values within the array
            closeelement(array, key, pos);

            // Return nothing                      
            return -2;  
        }
    }

    return -1;
}

Answer 1

Поскольку вы говорите, что этот алгоритм работает в отсортированных по возрастанию массивах, я могу подумать о следующих подходах:

1. Переключение доступа к индексу, т. Е. Вместо доступа к элементу по индексу i, доступ к элементу по array.Length - i - 1

   Пример:

   Вместо записи array[low] пишите array[array.Length - 1 - low]. Вы можете упростим это, введя переменную в начале метода:

   int l = array.Length - 1;
   

   Тогда в вашем коде сделайте например:

   while ((low <= high) && (key >= array[l - low]) && (key <= array[l - high])) 
   { /* ... */ }
   

2. Обратный массив перед выполнением алгоритма. Вы можете сделать это, используя Array.Reverse().

Answer 2

Предполагая, что вы хотите передать порядок, в котором массив был отсортирован в параметре order, вам просто нужно изменить условие завершения, например, (используя 0 = по убыванию, 1 = по возрастанию):

public static int interpo(double[] array, double key, int order)
{
    int low = 0, high = array.Length - 1;
    int pos = 0;
    int count = 0;

    while ((low <= high) && ((order == 1 && (key >= array[low]) && (key <= array[high])) || (order == 0 && (key <= array[low]) && (key >= array[high]))))
    {
        count++;
        pos = Convert.ToInt32(low + (high - low) / (array[high] - array[low]) *
            (key - array[low]));

        if (array[pos] == key)
        {
            // Write out the position and the value of whats in the position
            Console.WriteLine("\n     {0} : {1}", pos, array[pos]);
            break;
        }

        if (array[pos] < key)
            low = pos + 1;
        else
            high = pos - 1;

        // If the count is greater than the array size, do the following
        if (count > array.Length)
        {
            // Pass through the position within the array to the close element 
            // method, which will display the closest values within the array
            closeelement(array, key, pos);

            // Return nothing                      
            return -2;
        }
    }

    return -1;
}

EDIT

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

public static int interpo(double[] array, double key, int order)
{
    int low = 0, high = array.Length - 1;
    int pos = 0;
    int count = 0;

    while ((low <= high) && ((key <= array[low]) && (key >= array[high])))
    {
        count++;
        pos = Convert.ToInt32(low + (high - low) / (array[high] - array[low]) * 
            (key - array[low]));

        if (array[pos] == key)
        {
            // Write out the position and the value of whats in the position
            Console.WriteLine("\n     {0} : {1}", pos, array[pos]);                   
            break;
        }

        if (array[pos] < key)
            low = pos + 1;
        else
            high = pos - 1;

        // If the count is greater than the array size, do the following
        if (count > array.Length) 
        {
            // Pass through the position within the array to the close element 
            // method, which will display the closest values within the array
            closeelement(array, key, pos);

            // Return nothing                      
            return -2;  
        }
    }

    return - 1;
}