[每日coding]查找算法--插值查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[每日coding]查找算法--插值查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1270字，纯文字阅读大概需要2分钟。

内容图文

插值查找

算法简介

    插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式:

mid = low+(key-a[low])/(a[high]-a[low])*(high-low)。

算法思想

    基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
    注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

复杂度分析 

    时间复杂性：如果元素均匀分布，则O（log log n）），在最坏的情况下可能需要 O（n）。
    空间复杂度：O（1）。

代码实现

#include<iostream>

using namespace std;

int interpolation_search(int nums[], int begin, int end, int key){
    if (begin>=end) return -1;
    int mid = begin+((key-nums[begin])*(end-begin)/(nums[end]-nums[begin]));
    cout<<"debug: search: mid="<<mid<<endl;
    if(nums[mid]==key)
        return mid;
    else if(nums[mid]>key)
        return interpolation_search(nums,begin,mid-1,key);
    else
        return interpolation_search(nums,mid+1,end,key);
}

int main(){
    int nums[] = {1,3,4,6,8,9,10,13,16,19,20,21};
    int len = sizeof(nums)/sizeof(nums[0]);
    int key, location;
    cin >> key;
    location = interpolation_search(nums, 0, len-1, key);
    if(location == -1)
        cout<<key<<" is no in nums"<<endl;
    else
        cout<<key<<" is at: "<<location<<endl;
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的[每日coding]查找算法--插值查找全部内容，希望文章能够帮你解决[每日coding]查找算法--插值查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---