插值搜索，在降序数组上搜索 [英] Interpolation Search, searching on a descending array

问题描述

我想修改此算法，以便它可以找到数组中按降序排序的值。当前仅适用于升序。

I want to modify this algorithm so that it can find values within an array which has been sorted in descending order. This currently only works for ascending.

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

推荐答案

假设您希望要传递参数 order 中数组的排序顺序，您只需要更改终止条件即可（使用0 = descending，1 = ascending） ：

Assuming you want to be able to pass the order in which the array has been sorted in the parameter order, you just need to change your termination condition, like so (using 0=descending, 1=ascending):

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

编辑

如果您需要函数仅能够在降序数组中查找值，只需更改终止条件，如下所示：

If you need the function to only be able to find values in a descending array, just change your termination condition like so:

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

这篇关于插值搜索，在降序数组上搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！