C#实现插值查找算法

C#实现插值查找算法

插值查找(Interpolation Search)是一种改进的二分查找算法,它在有序数组中查找时利用了数组中元素的分布信息来进行搜索,从而在某些情况下比二分查找更高效。插值查找的核心思想是通过估计要查找的值在数组中的位置,从而减少查找范围。

下面是一个用C#实现的插值查找算法的示例:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
        int n = arr.Length;
        int x = 18; // 要查找的元素
        int index = InterpolationSearch(arr, x);

        if (index != -1)
            Console.WriteLine($"Element found at index {index}");
        else
            Console.WriteLine("Element not found");
    }

    static int InterpolationSearch(int[] arr, int x)
    {
        int lo = 0, hi = arr.Length - 1;

        while (lo <= hi && x >= arr[lo] && x <= arr[hi])
        {
            if (lo == hi)
            {
                if (arr[lo] == x) return lo;
                return -1;
            }

            int pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

            if (arr[pos] == x)
                return pos;

            if (arr[pos] < x)
                lo = pos + 1;
            else
                hi = pos - 1;
        }
        return -1;
    }
}

代码解释

  1. 主函数(Main):

    • 创建了一个有序数组arr,并定义了要查找的元素x
    • 调用InterpolationSearch函数查找元素x在数组中的位置,并打印结果。
  2. 插值查找函数(InterpolationSearch):

    • 初始化低端索引lo和高端索引hi
    • 进入while循环,在lo小于等于hix在数组范围内的情况下进行查找。
    • 如果lohi相等,直接判断arr[lo]是否等于x,是则返回索引,否则返回-1
    • 计算估计位置pos
    • 如果arr[pos]等于x,返回pos
    • 如果arr[pos]小于x,调整lopos + 1,否则调整hipos - 1
    • 如果查找失败,返回-1

这个算法在数据均匀分布的情况下性能会很好,最坏情况下的时间复杂度是O(n)。对于非均匀分布的数据,性能可能会退化,接近于线性查找。

C#实现插值查找算法

插值查找(Interpolation Search)是一种改进的二分查找算法,它在有序数组中查找时利用了数组中元素的分布信息来进行搜索,从而在某些情况下比二分查找更高效。插值查找的核心思想是通过估计要查找的值在数组中的位置,从而减少查找范围。

下面是一个用C#实现的插值查找算法的示例:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
        int n = arr.Length;
        int x = 18; // 要查找的元素
        int index = InterpolationSearch(arr, x);

        if (index != -1)
            Console.WriteLine($"Element found at index {index}");
        else
            Console.WriteLine("Element not found");
    }

    static int InterpolationSearch(int[] arr, int x)
    {
        int lo = 0, hi = arr.Length - 1;

        while (lo <= hi && x >= arr[lo] && x <= arr[hi])
        {
            if (lo == hi)
            {
                if (arr[lo] == x) return lo;
                return -1;
            }

            int pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

            if (arr[pos] == x)
                return pos;

            if (arr[pos] < x)
                lo = pos + 1;
            else
                hi = pos - 1;
        }
        return -1;
    }
}

代码解释

  1. 主函数(Main):

    • 创建了一个有序数组arr,并定义了要查找的元素x
    • 调用InterpolationSearch函数查找元素x在数组中的位置,并打印结果。
  2. 插值查找函数(InterpolationSearch):

    • 初始化低端索引lo和高端索引hi
    • 进入while循环,在lo小于等于hix在数组范围内的情况下进行查找。
    • 如果lohi相等,直接判断arr[lo]是否等于x,是则返回索引,否则返回-1
    • 计算估计位置pos
    • 如果arr[pos]等于x,返回pos
    • 如果arr[pos]小于x,调整lopos + 1,否则调整hipos - 1
    • 如果查找失败,返回-1

这个算法在数据均匀分布的情况下性能会很好,最坏情况下的时间复杂度是O(n)。对于非均匀分布的数据,性能可能会退化,接近于线性查找。

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在