文档章节

斐波那契查找

laomd
 laomd
发布于 2017/02/24 13:40
字数 492
阅读 8
收藏 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
1K
0
(8)《数据结构与算法》之查找算法

在java中,我们常见的查找有四种 顺序查找,也叫线性查找 二分查找,也叫折半查找 插值查找 斐波那契查找 我们将一一介绍着四种查找方式的思想以及程序的实现。 1.顺序查找 顺序查找 的查找过...

行走在代码边缘
06/21
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
954
0
JS专题之memoization

前言 在计算机领域,记忆(memoization)是主要用于加速程序计算的一种优化技术,它使得函数避免重复演算之前已被处理过的输入,而返回已缓存的结果。 -- wikipedia 的原理就是把函数的每次执...

南波
02/08
0
0
数据结构与算法之递归和分治思想

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

aibinxiao
2018/07/01
105
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部