13518219792
本篇内容介绍了“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++有序表查找的方法是什么”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
