文档章节

斐波那契查找

laomd
 laomd
发布于 2017/02/24 13:40
字数 492
阅读 5
收藏 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;
}

 

© 著作权归作者所有

共有 人打赏支持
laomd
粉丝 0
博文 31
码字总数 12000
作品 0
广州
斐波那契查找(黄金分割法查找)

什么是斐波那契查找 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n...

serenity
2014/06/20
0
0
"二分查找(Binary Search)"与"斐波那契查找(Fibonacci Search)"

首先,我们来看一个笔者的拙作,一段二分查找代码 //返回值是key的下标,如果A中不存在key则返回-1template <class T>int BinSearch(T* A, const T &key, int lo, int hi){ int mid; while(l...

不高不富不帅的陈政_
2015/09/30
573
0
科普向 - 趣味的斐波那契数列

1.从一道面试题开始 每个程序员从第一次接触计算机编程语言到真正作为工程师进行项目开发,都一定都见过下面这道题目: 很多个台阶,可以一次走一个台阶,也可以一次走两个台阶,那么走台阶时...

ssssyoki
08/11
0
0
数据结构与算法之递归和分治思想

一、递归 1.递归的定义 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法叫做递归, 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略...

aibinxiao
07/01
0
0
斐波那契数

一、题目: 递归和非递归分别实现求第n个斐波那契数。 二、解题思路: 先了解下斐波拉契数列 (1 1 2 3 5 8 13 21 34 55···),第n个斐波那契数等于(n-1)个斐波那契数加上(n-2)个斐波那...

qq_38646470
2017/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

实战讲解高并发和秒杀抢购系统设计

互联网特别是电商平台,阿里双11秒杀、还有12306春运抢票、以及平时各种节假日抢购活动等,都是典型的高并发场景。 这类场景最大的特征就是活动周期短,瞬间流量大(高并发),大量的人短期涌...

xtof
17分钟前
0
0
代码质量管理平台-sonarqube

在工作中,往往开发的时候会不怎么注重代码质量的人很多,存在着很多的漏洞和隐患等问题,sonarqube可以进行代码质量的审核,而且十分的残酷。。。。。接下来我们说下怎么安装 进入官网下载:...

落叶清风
20分钟前
4
0
在Ubuntu安装和配置Sphinx

Ubuntu系统默认是配置有sphinx的,先检查一下,别多此一举。。。。。 在开始本指南之前,您需要: 一个Ubuntu 16.04服务器。 sudo的一个非root用户,您可以通过以下设置本教程 。 安装在服务...

阿锋zxf
29分钟前
0
0
Qt编写输入法V2018超级终结版

对于qt嵌入式linux开发人员来说,输入法一直是个鸡肋问题,要么不支持实体键盘同步,要么不能汉字输入,要么不支持网页输入等,这几年通过陆续接触大量的各种输入法应用场景客户,得到真实需...

飞扬青云
40分钟前
0
0
TypeScript基础入门之高级类型的多态的 this类型

转发 TypeScript基础入门之高级类型的多态的 this类型 高级类型 多态的this类型 多态的this类型表示的是某个包含类或接口的子类型。 这被称做F-bounded多态性。 它能很容易的表现连贯接口间的...

durban
46分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部