c++有序表查找的方法是什么

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