数据结构之---C语言实现斐波那契查找

斐波那契查找的核心思想是:

1)当key=a[mid]时,查找成功;

2)当key<a[mid]时,新的查找范围是第low个到第mid-1个,此时范围个数为F[k-1] - 1个,即数组左边的长度,所以要在[low, F[k - 1] - 1]范围内查找;

3)当key>a[mid]时,新的查找范围是第mid+1个到第high个,此时范围个数为F[k-2] - 1个,即数组右边的长度,所以要在[F[k - 2] - 1]范围内查找。

代码:

//斐波那契查找
//杨鑫
#include <stdio.h>
#include <stdlib.h>
#define MAXN 20

/*
 *产生斐波那契数列
 * */
void Fibonacci(int *f)
{
	int i;
	f[0] = 1;
	f[1] = 1;
	for(i = 2;i < MAXN; ++i)
		f[i] = f[i - 2] + f[i - 1];
}

/*
 * 查找
 * */
int Fibonacci_Search(int *a, int key, int n)
{
	int i, low = 0, high = n - 1;
	int mid = 0;
	int k = 0;
	int F[MAXN];
	Fibonacci(F);
	while(n > F[k] - 1) 			//计算出n在斐波那契中的数列
		++k;
	for(i = n;i < F[k] - 1;++i) //把数组补全
		a[i] = a[high];
	while(low <= high)
	{
		mid = low + F[k-1] - 1;  //根据斐波那契数列进行黄金分割
		if(a[mid] > key)
		{
			high = mid - 1;
			k = k - 1;
		}
		else if(a[mid] < key)
		{
			low = mid + 1;
			k = k - 2;
		}
		else
		{
			if(mid <= high) //如果为真则找到相应的位置
				return mid;
			else
				return -1;
		}
	}
	return 0;
}

int main()
{
	int a[MAXN] = {5,15,19,20,25,31,38,41,45,49,52,55,57};
	int k, res = 0;
	printf("请输入要查找的数字:\n");
	scanf("%d", &k);
	res = Fibonacci_Search(a,k,13);
	if(res != -1)
		printf("在数组的第%d个位置找到元素:%d\n", res + 1, k);
	else
		printf("未在数组中找到元素:%d\n",k);
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-28

数据结构之---C语言实现斐波那契查找的相关文章

斐波那契查找算法 -数据结构

这个是我本人写的斐波那契查找算法,和网上的其他思路略有不同,特贴出来: 1)没有预先存储斐波那契的数组,整个的搜索数据长度可以变动: 2)mid索引的变动是动态变化的,根据斐波那契的回退方法: #include<stdlib.h>#include<stdio.h> #define INF 32767#define SIZE 92int Feibinaci(int str[],int n,int key){ int F0 = 1; int F1 = 1; int temp; int

看数据结构写代码(53) 静态查找表(线性查找,二分查找,斐波那契查找,插值查找)

查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录). 查找表分类:静态查找表和动态查找表. 静态查找表:只查找,而不进行插入,删除. 动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素. 静态表的 查找 大致 四种 算法: 线性查找,二分查找,斐波那契查找和插值查找. 其中 在线性查找之前,对表 无要求.对于 其余三种 需要 在查找之前 排序.插值查找 除了 需要 排序,还需要 均匀分布. 下面 给出代码: 线性查

数据结构(六)查找---有序表查找(三种查找方式:折半,插值,斐波拉契查找)

前提 有序表查找要求我们的数据是有序的,是排序好的,我们只需要进行查找即可 我们下面将介绍折半查找(二分查找),插值查找,斐波那契查找 一:折半查找 (一)定义 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法.但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列. (二)查找过程 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关

"二分查找(Binary Search)"与"斐波那契查找(Fibonacci Search)"

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

【算法】先生,您点的查找套餐到了(二分、插入和斐波那契查找)

参考资料 <算法(java)>                           — — Robert Sedgewick, Kevin Wayne <数据结构>                                  — — 严蔚敏 Interpolation Search[插值查找]     — —  维基百科 Fibonacci Search[斐波那契查找]   — —  GeeksforGeeks 根据输入的一个关键字(Key),  在一个有序数组内查找与该关键

斐波那契查找(超详解)

// 斐波那契查找.cpp #include <iostream> #include <string.h> using namespace std; const int max_size=20;//斐波那契数组的长度 /*构造一个斐波那契数组*/ void Fibonacci(int * F) { F[0]=0; F[1]=1; for(int i=2;i<max_size;++i) F[i]=F[i-1]+F[i-2]; } /*定义斐波那契查找法*/ int Fibona

二分查找和斐波那契查找

二分查找 说明:查找的数组或列表必须是有序的,若无序,先进行排序 复杂度:时间复杂度 O(log2n),空间复杂度O(n) C++源码(递归和非递归两个版本) #include <iostream> using namespace std; int a[] = { 1, 2, 3, 4, 5, 6, 8 }; int BinarySearch1(int l, int r, int value) { int mid = (l + r) / 2; if (l == r && a[l

斐波那契查找原理详解与实现

最近看见一个要求仅使用加法减法实现二分查找的题目,百度了一下,原来要用到一个叫做斐波那契查找的的算法.查百度,是这样说的: 斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的.他要求开始表中记录的个数为某个斐波那契数小1,即n=F(k)-1;  开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种  1)相等,mid位置的元素即为所求  2)>   ,low=mid+1,k-=2;说明:low=mid+1说明待查找的元素在

斐波那契查找算法完整C代码

/* 斐波那契查找法 */ #include <stdio.h> #include <stdlib.h> int Fib( int k ) { if( 1 == k || 2 == k ) return 1; else return Fib(k-1)+Fib(k-2); } int FibSearch( int *a, int n, int key ) { int k = 1; int nFib; int *b; int low, mid, high; while( Fib(k)