斐波那契查找
博客专区 > laomd 的博客 > 博客详情
斐波那契查找
laomd 发表于11个月前
斐波那契查找
  • 发表于 11个月前
  • 阅读 5
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

楼主建议小伙伴们先学习折半查找 插值查找之后再来看这篇博客,因为斐波那契查找算法是从折半查找思想衍生的,如果能弄懂折半查找,斐波那契查找也就不在话下了。

       我们知道,不论是折半、插值查找,都涉及到对原有数据串的分割,折半插值是每次各一半,插值查找每次按比例分割,其实斐波那契查找也是同理。它的分割,是把一个长度为F[k](F是一个斐波那契数列)的数据串每次分割成左边的F[k-1]和右边的F[k-2],当然也可以倒过来。

        可能有些爱抬杠的小伙伴就说了,若果我的数组长度不是一个斐波那契数呢?很简单啊,一直push_back()直到长度等于第一个比原长度大的斐波那契数

        下面是代码,与折半查找类似:

//模仿STL查找的规则,在左闭右开[low,high)区间查找key
//如果找到,返回其位置(1,2,3,4,······),否则返回0
int fibsearch(const vector<int>& v, int low, int high, const int& key)
{
	int n = v.size();

    //生成一个斐波那契数列
	vector<int> F;
	F.push_back(0);
	F.push_back(1);
	int k = 1;
	while(F.back() < n) {
	    F.push_back(F[k - 1] + F[k - 2]);
	    k++;
	}

	vector<int> newvector = v;
    
    //多出来的长度用来存放v的最后一个元素
	int newsize = F.back(), i = n, e = v.back();
	while(i < newsize) {
	    newvector.push_back(e);
	    i++;
	}
    
    //此时newvector的长度为F[k],也就是F.back()
	while(low < high) {
	    int pos = low + F[k - 1];//可能有些版本写作int pos = low + F[k - 1] - 1,因为他们是[low,high]
	    if(v[pos] == key)
	    {
	    	if(pos >= n)//说明是在后来push_back()到newvector的元素中找到
	    		return n;
	    	else
	    		return pos + 1;
	    }
	    else
	    	if(v[pos] < key)//进入右端,长度为F[k-2],故k -= 2
	    	{
	    		low = pos + 1;
	    		k -= 2;
	    	}
	    	else//进入左端,长度为F[k-1],故 k -= 1;
	    	{
	    		high = pos;
	    		k--;
	    	}
	}
	return 0;
}

 

标签: 查找算法
共有 人打赏支持
粉丝 0
博文 31
码字总数 12000
×
laomd
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: