查找算法——插值查找法

一、介绍 

        插值查找法是二分查找的改进版，同样的它需要查找的数据也是有序的，它是按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近。使用这种查找方法需要数据是平均分布的，而且每一项数据的差距相当接近或有一定的距离比例，也就是说每两项数据的差值的大小差别不能太大或者每两项数据的之间的差值都有一定比例的，数据之间分布是均匀的，因为这种方式用要查找的数据值与区间最小值的差与区间范围的比值来确定数据的大概范围，所以就限定了要查找的数据的所需条件。

插值查找法的公式为：

其中key是要查找数据，data[high]、data[Low]是剩余待查找记录中的最大值和最小值。

查找的步骤如下:

1.确实要查找的数据是有序的或者将要查找的数据排序。

2.令low =0，high= 数据的长度 -1。

3.当low < high 时，重复 步骤4和5。

4.令

5.若 key < keyMid 且 high != Mid -1,则令high =  Mid -1。

6.若key = keyMid, 表示成功找到该值。

7.若key>keyMid,且low!=Mid -1,则令low=Mid+1;

演示如下：

 二、代码实现：

using System.Collections.Generic;
using UnityEngine;
 
public class InterpolationLookUpArithmetic : MonoBehaviour
{
    List<int> data;
 
    [SerializeField]
    int dataLength = 100;
 
    int needData = 0;
 
    private void Start()
    {
        data = new List<int>(dataLength);
        InitData(dataLength);
        InterpolationLookUp(needData);
    }
 
    void InitData(int datalen)
    {
        for (int i = 0; i < datalen; i++)
        {
            data.Add(i);
 
            if (i > 40 && needData == 0)
                needData = i + Random.Range(-10,10);
        }
    }
 
    void InterpolationLookUp(int val)
    {
        int low, high, mid;
        low = 0;
        high = data.Count - 1;
 
        if (val < data[low] || val > data[high])
        {
            Debug.LogError("数据不在要查找的数据范围内。");
            return;
        }
 
        while (low <= high)
        {
            mid = low + (val - data[low]) / (data[high] - data[low]) * (high - low);
 
            //首先要确定这个mid的值是否是在可用范围内
            if (mid > high || mid < low)
            {
                Debug.LogError("mid超出范围");
                return;
            }
 
            //然后要确定这时的val和data[low]、data[high]的大小关系,确定val是否在区间范围内
            if (val < data[low] && val < data[high])
            {
                Debug.LogError("数值未达到数据范围");
                return;
            }
 
            else if (val > data[low] && val > data[high])
            {
                Debug.LogError("数值超出数据范围");
                return;
            }
                
            //以下就是类似二分法的步骤
            if (val == data[mid])
            {
                Debug.Log("找到该值");
                return;
            }
            else if (val < data[mid])
            {
                high = mid - 1;
            }
            else if (val > data[mid])
            {
                low = mid + 1;
            }
        }
 
        Debug.LogError("没有查找到数据");
    }
}

参考书籍：

清华大学出版社-图书详情-《图解数据结构--使用C#》 (tsinghua.edu.cn)