本篇内容介绍了“c++有序表查找的方法是什么”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
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(key<a[mid])
{
high=mid-1;
}
else if(key>a[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(key<a[mid])
{
high = mid-1;
}
else if(key>a[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;i<F[k]-1;i++)
{
a[i]=a[n-1];
}//将斐波那契数列 不满地方补全
while(low<=high)
{
mid = low+F[k-1]-1;
if(key<a[mid])
{
high = mid-1;
k=k-1;
}
else if(key>a[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++有序表查找的方法是什么”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4511602/blog/4826600