【算法学习3.2】插值查找算法以及C++实现

插值查找

在算法学习3.1中提到的二分查找，即折半查找同理的查找算法。折半查找是每次取区间的一半，那可不可以取1/3、1/4这样呢。如果查找区间过长，那么折半查找所需要的时间一定也会非常长。如果能够提前知道目标数据在区间的大概位置，是否可以直接到那个大概位置去寻找呢。

奥夫考斯！

插值查找的基本原理：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

关键代码如下

int Search(int a[], int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);

    if(a[mid]==value){
        return mid;
    }

    if(a[mid]>value){
        return Search(a, value, low, mid-1);
    }

    if(a[mid]

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/675978.html