c++有序表查找的方法是什么
本篇内容介绍了“c++有序表查找的方法是什么”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
成都创新互联是一家专业提供防城港企业网站建设,专注与成都网站设计、成都做网站、H5技术、小程序制作等业务。10年已为防城港众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。
1.折半查找法-binary search
如果线性表在排序是有序的 这种情况下我们才用顺序存储。
//折半查找法 int BinarySearch(int* a,int n, int key) { int low=0; int high=n-1; while(low<=high) { int mid = (low+high)/2; if(keya[mid]) { low = mid+1; } else return mid; } return -1;//表示失败 }
折半查找法类似于把静态有序查找表分成了两颗子树,时间复杂度为O(log N),当我们对顺序数据已经排序好,并且没有频繁插入删除时用折半查找法。
2.插值查找法
我们在字典中查找apple或者zoo一定不是按照折半查找法这样 会直接从前面或者后面查找,
不一定非要mid=(low+high)/2;
mid=(low+high)/2=low+(high-low)/2;
mid = low+(high-low)((key-a[low])/(a[high]-a[low]) )
//插值查找法 int BinarySearch(int* a, int n, int key) { int low=0; int high = n-1; while(low<=high) { int mid = low+(low+high)*((key-a[low])/(a[high]-a[low])); if(keya[mid]) { low=mid+1; } else { return mid; } } return -1; }
此时时间复杂度还是O(longN),当关键字分部比较均匀时候可用此法。
3.斐波那契查找O(log N)
//斐波那契数列 void Fibonacci() { int F[100]; F[0]=0; F[1]=1; for(int i=2;i<=100;i++) { F[i]=F[i-1]+F[i-2]; } } int Fibonacci_Search(int* a, int n, int key) { int k=0; int low=0; int high=n-1; while(n>F[k]-1)//计算n位于斐波那契数列的位置 { k++; } for(int i=n-1;ia[mid]) { low = mid+1; k=k-2; } else { if(mid<=n-1) { return mid; } else { return -1;//失败 } } } }
应当说 当顺序存储无序时 采用顺序查找法
当顺序存储已经排序好 我们可以采用折半查找法mid=(low+high)/2;
插值查找法mid=low+(high-low)*((key-a[low])/(a[high]-a[low]));
斐波那契法mid=low+F[k-1]=1;
以上三中算法无非就是mid 选取的不一样而已 不过在mid 选取时候也有加减乘除计算的。
“c++有序表查找的方法是什么”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
当前名称:c++有序表查找的方法是什么
转载源于:http://pwwzsj.com/article/gidjij.html