提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

插值查找

查找 插值
2023-06-13 09:15:42 时间

概要

1.插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查。

2.将这般查找中的求mid索引的公式，low表示左边索引，high表示右边索引。

key就是我们前面说的findval

3.int midIndex = low + (high - low) * (key -arr[low]) / (arr[high] - arr[low]); //插值索引

对应前面的代码公式：

int mid = left + (right - left) * (findval - arr[left]) / (arr[right] - arr[left])

4.举例说明插值查找算法1-100的数组

  • 已有数组arr=[1,2,3....,100];
  • 假如我们需要查找的值为1
  • 使用二分查找的话，我们需要多次递归，才能1
  • 使用插值查找算法 int mid = left + (right - left) * (findval - arr[left]) / (arr[right] - arr[left])
  • 0 = 0 + (99 - 0) * (1 - 1) / { 100 - 1 } 只需要比对一次。而二分查找需要比对四次。
  1. 对于数据量较大，关键字分部比较均匀的查找表来说，采用插值查找，速度较快。
  2. 关键子分布不均匀的情况下，该方法不一定比折半查找要好。

代码

  public class InsertValueSearch
    {
        /// <summary>
        /// 插值查找算法(需要数组是有序的)
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="left">左边索引</param>
        /// <param name="right">右边索引</param>
        /// <param name="findval">查找值</param>
        /// <returns>值的下标</returns>
        public static int Search(int[] arr, int left,int right,int findval)
        {
            //必须需要，否则得到的mid的值可能越界。
            if (left > right || findval < arr[0] || findval > arr[arr.Length - 1])
            {
                return -1;
            }
            //求出mid
            int mid = left + (right - left) * (findval - arr[left]) / (arr[right] - arr[left]);
            int midVal = arr[mid];
            if (findval > midVal)
            {
                //说明应该向右边进行查找
                return Search(arr, mid + 1, right, findval);
            }
            else if (findval < midVal)
            {
                return Search(arr, left, mid - 1, findval);
            }
            else
            {
                return mid;
            }
        }
    }

调用

        static void Main(string[] args)
        {
            //数组进行升序排序
            int[] arr = { 1, 8, 10, 89, 1000, 1234 };
            var result = InsertValueSearch.Search(arr, 0,arr.Length -1 , 1000);
            Console.WriteLine(result);
            Console.Read();
        }

插值查找VS二分查找，性能对比

    static void Main(string[] args)
        {
            //初始化一个有序的100长度的数组
            int[] arr = new int[100];
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = i + 1;
            }
            //使用二分查找，并在方法内部加一个打印，输出几次代表执行了几次
            var result = BinarySearch.Search(arr,0,arr.Length,100);
            //使用插值查找，并在方法内部加一个打印，输出几次代表执行了几次
            var result0 = InsertValueSearch.Search(arr, 0,arr.Length -1 , 1000);
            Console.Read();
        }

肉眼可见的差距！！！

相关文章