C#查找算法2：插值查找

明志德道

发布于 2023-10-21 17:41:12

1620

发布于 2023-10-21 17:41:12

文章被收录于专栏：明志德到的IT笔记

插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。

原理： (midIndex-lowIndex) /(highIndex-lowIndx) 的比值 ≈≈(value-a[low])/(a[high]-a[low])）的比值

代码如下

      /// <summary>
        /// 插值查找
        /// </summary>
        /// <param name="arr">数组</param>
        /// <param name="low">初始索引</param>
        /// <param name="high">末尾索引</param>
        /// <param name="value">要找的值</param>
        /// <returns></returns>
        static int InsertSearch(int[] arr,int low,int high,int value)
        {
            if (arr == null || arr.Length == 0 || low >= high)
            {
                return -1;
            }
            int mid;
            while (low <= high)
            {
                mid  = low+((value - arr[low]) / (arr[high] - arr[low]))*(high-low);// 插值查找的核心代码
                if (value > arr[mid])//值在arr[mid]的右边
                {
                    low = mid + 1;
                }
                if(value<arr[mid])//值在arr[mid]的左边
                {
                    high = mid - 1;
                }
                if(value==arr[mid])
                {
                    return mid;
                }
            }
            return -1;
        }

其实还有第二种写法，递归，写法差不多，不会的去看我的上一篇“二分查找”

运行结果

           Console.WriteLine($"数据算法");
            Random random = new Random();

            var arr1 = GetArrayData(20, 1,15 );
            Console.WriteLine($"生成未排序数据arr1：{ShowArray(arr1)}");

            var arr5 = QuickSort(arr1, 0, arr1.Length - 1);
            Console.WriteLine($"快速排序arr5：{ShowArray(arr5)}");

            var randomIndex = random.Next(0, arr5.Length);
            var arr5Index= InsertSearch(arr5, 0, arr5.Length - 1, arr5[randomIndex]);
            Console.WriteLine($"{arr5[randomIndex]}在 arr5中出现的索引位置是{arr5Index}");

            Console.ReadLine();