文档章节

斐波那契查找

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

没有更多内容

加载失败,请刷新页面

加载更多

EOS docker开发环境

使用eos docker镜像是部署本地EOS开发环境的最轻松愉快的方法。使用官方提供的eos docker镜像,你可以快速建立一个eos开发环境,可以迅速启动开发节点和钱包服务器、创建账户、编写智能合约....

汇智网教程
今天
10
0
《唐史原来超有趣》的读后感优秀范文3700字

《唐史原来超有趣》的读后感优秀范文3700字: 作者:花若离。我今天分享的内容《唐史原来超有趣》这本书的读后感,我将这本书看了一遍之后就束之高阁了,不过里面的内容一直在在脑海中回放,...

原创小博客
今天
16
0
IC-CAD Methodology知识图谱

CAD (Computer Aided Design),计算机辅助设计,指利用计算机及其图形设备帮助设计人员进行设计工作,这个定义同样可以用来近似描述IC公司CAD工程师这个岗位的工作。 早期IC公司的CAD岗位最初...

李艳青1987
今天
16
0
CompletableFuture get方法一直阻塞或抛出TimeoutException

问题描述 最近刚刚上线的服务突然抛出大量的TimeoutException,查询后发现是使用了CompletableFuture,并且在执行future.get(5, TimeUnit.SECONDS);时抛出了TimeoutException异常,导致接口响...

xiaolyuh
今天
8
0
dubbo 搭建与使用

官网:http://dubbo.apache.org/en-us/ 一,安装监控中心(可以不安装) admin管理控制台,monitor监控中心 下载 bubbo ops 这个是新版的,需要node.js环境,我没有就用老版的了...

小兵胖胖
今天
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部