基于二分查找的其他查找算法

1.fibonacci​查找。

每次将区间$[l,r]$分为两部分，$fib[idx-1],fib[idx-2]$。

每次令$mid=l+fib[idx-1]-1$，也即$fib[idx-1]$的右端点，特判。

如果$a[mid]==val$ 直接返回对应位置的值即可。

否则如果$a[mid]>val$，则继续对区间左端查找$idx–,r=mid-1$。

否则对区间右端进行查找，$idx-=2,l=mid+1$。

因为二分查找需要进行除法运算，而$fibonacci$查找只需用到加减法，所以在数据量较大时，$fibnacci$查找更优的。

代码

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
ll f[105];
vector<int>a;
void pre(int n){
    f[1]=f[2]=1;
    for(int i=3;i<=n;i++){
        f[i]=f[i-1]+f[i-2];
    }
} 
int  fib_search(vector<int>a,int val){
    int idx=0,m=a.size();pre(20);
    while(f[idx]<a.size()){
        idx++;
    }
    for(int i=a.size();i<f[idx];i++){
        a.pb(a[a.size()-1]);
    } 
    int l=0,r=a[a.size()-1];
    while(l<=r&&idx>=0){
        int mid=l+f[idx-1]-1;
        if(a[mid]==val)    return mid>=m?m-1:mid;
        else if(a[mid]>val) r=mid-1,idx--;
        else l=mid+1,idx-=2;
    }return -1;
}
int main(){
    freopen("1.in","r",stdin);
    for(int i=0,x;i<10;i++){
        scanf("%d",&x);a.pb(x);
    }sort(a.begin(),a.end());
    printf("查询的结果为:\n");
    printf("%d\n",fib_search(a,7));
    return 0;
}

$tips:$

$fibonacci$ 在第$47$项爆$int$。

在第$93$项爆$long\ long$。

---

2.插值查找。

只需将二分查找的$mid=l+\dfrac{r-l}{2}$改成$mid=l+\dfrac{(val-a[l])}{a[r]-a[l]}\times (r-l)$。

这样的算法在数组长度较大，且分布平均的数组中时间复杂度更优。

时间复杂度：$O(loglogn)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int a[N],n;
int ins_search(int *a,int val){
    int l=1,r=n;
    while(l<=r){
        int mid=l+(val-a[l])/(a[r]-a[l])*(r-l);
        if(a[mid]==val) return mid;
        else if(a[mid]>val) r=mid-1;
        else l=mid+1;
    }
    return -1;
}
int main(){
    freopen("2.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1); 
    printf("查询结果为:\n");
    printf("%d\n",ins_search(a,7));
    return 0;
}

---