插值搜索，在降序数组上搜索

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

假设你希望能够在参数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;
}

编辑

如果您需要仅能够在降序数组中查找值的函数，只需像这样更改终止条件：

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 2

既然你说这个算法适用于升序排列的数组，我可以想到以下方法：

切换索引访问，即不访问索引 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])) 
{ /* ... */ }
```
在执行算法之前反转数组。您可以使用 Array.Reverse() 执行此操作。

插值搜索，在降序数组上搜索

Interpolation Search, searching on a descending array

c#

arrays

sorting

algorithm

interpolation