数据检索算法是指从数据集合（数组、表、哈希表等）中检索指定的数据项。

数据检索算法是所有算法的基础算法之一。

本文提供插值搜索（Interpolation Search）的源代码。

1 文本格式

using System;

namespace Legalsoft.Truffer.Algorithm
{
    public static class ArraySearch_Algorithm
    {
        /// <summary>
        /// 插值搜索
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <param name="x"></param>
        /// <returns></returns>
        public static int Interpolation_Search(int[] arr, int left, int right, int x)
        {
            int pos;
            if (left <= right && x >= arr[left] && x <= arr[right])
            {
                pos = left + (((right - left) / (arr[right] - arr[left])) * (x - arr[left]));
                if (arr[pos] == x)
                {
                    return pos;
                }
                if (arr[pos] < x)
                {
                    return Interpolation_Search(arr, pos + 1, right, x);
                }
                if (arr[pos] > x)
                {
                    return Interpolation_Search(arr, left, pos - 1, x);
                }
            }
            return -1;
        }

    }
}
 

————————————————————

POWER BY TRUFFER.CN

2 代码格式

using System;

namespace Legalsoft.Truffer.Algorithm
{
    public static class ArraySearch_Algorithm
    {
        /// <summary>
        /// 插值搜索
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <param name="x"></param>
        /// <returns></returns>
        public static int Interpolation_Search(int[] arr, int left, int right, int x)
        {
            int pos;
            if (left <= right && x >= arr[left] && x <= arr[right])
            {
                pos = left + (((right - left) / (arr[right] - arr[left])) * (x - arr[left]));
                if (arr[pos] == x)
                {
                    return pos;
                }
                if (arr[pos] < x)
                {
                    return Interpolation_Search(arr, pos + 1, right, x);
                }
                if (arr[pos] > x)
                {
                    return Interpolation_Search(arr, left, pos - 1, x);
                }
            }
            return -1;
        }

    }
}