郫县城乡规划建设管理局网站,万网站长工具,专门做图标的网站,wordpress文章列表加广告两个查找算法都是针对有序数组进行查找#xff0c;不同点在于分界点的取值不同。
算法介绍
折半查找很简单#xff0c;每次与当前区间的中点进行比较#xff0c;然后决定查找前一部分还是后一部分。
Fibonacci查找利用了Fibonacci序列每一项等于前两项和的特点进行划分不同点在于分界点的取值不同。
算法介绍
折半查找很简单每次与当前区间的中点进行比较然后决定查找前一部分还是后一部分。
Fibonacci查找利用了Fibonacci序列每一项等于前两项和的特点进行划分然后再在前一部分或者后一部分进行查找。
对于一个数组我们首先将他填充成长度为F[k]-1的数组其中F[]表示斐波那契数列。为什么非要填充成F[k]-1呢
我们知道斐波那契数列有如下性质 F[k]F[k−1]F[k−2]F[k]F[k-1]F[k-2] F[k]F[k−1]F[k−2] 朴素的想法是我们对区间[l,r)进行划分其中r-lF[k]分界点选择为midlF[k-1](当然我们也可以选择F[k-2]这取决于数据集中在哪里)。当我们将需要查询的数据x和a[mid]比较以后我们可能需要查询左边或者右边的区间即[l,mid)或者[mid1,r)而这个时候后面那个区间的长度为F[k-2]-1不再是斐波那契数列。这显然不是我们想要看到的结果。
我们不妨尝试将区间的长度变成F[k]-1将分界点设置为midlF[k-1]-1,这时我们发现右边的区间的长度将变成F[k-2]-1仍旧满足这种结构。这样我们就可以递归地进行处理。
我们也可以尝试将区间长度变为F[k]1只是这样的话我们就无法将区间长度变为0退出搜索。
实现代码
#includecstdio
#includealgorithm
#includecstdlibusing namespace std;int init(int* F,int n)
{F[0]1;F[1]1;int ret2;while(1){F[ret]F[ret-1]F[ret-2];if(F[ret]-1n)break;ret;}return ret;
}
int FiboSearch(int *a,int *F,int k,int l,int r,int x)
{if(rl) return -1;int midlF[k-1]-1;if(xa[mid]) return mid;if(xa[mid]){return FiboSearch(a,F,k-1,l,mid,x);}else{return FiboSearch(a,F,k-2,mid1,r,x);}
}
int main()
{int n,k;printf(n); scanf(%d,n);printf(k); scanf(%d,k);int F[64],len;int a[128];leninit(F,n);for(int i0;in;i){scanf(%d,a[i]);}if(ka[n-1] || ka[0]){printf(-1\n);return 0;}printf(%d\n,FiboSearch(a,F,len,0,F[len]-1,k));return 0;
}
性能分析
斐波那契查找算法同折半查找一样复杂度都是O(logn)的不同点在于当数据是均匀分布的时候折半查找更加优秀当数据是指数分布的时候斐波那契查找算法更好。
