斐波那契搜索 [英] Fibonacci Search

问题描述

有人请给我解释一下斐波那契搜索算法。

我身边有试过无数的资源，并搜查了很多，但该算法还不清楚。大多数资源的二进制搜索链接描述它，但我不明白他们。我知道斐波纳契搜索算法是二进制搜索，我知道很好的延伸。

我的书没有解释为好。

我是知道的定义为F（n）的斐波那契数= F（N-1）+ F（N-2），所以没有必要解释。

加入究竟是什么我听不懂的@AnthonyLabarre说更新的问题：

我用这本书有奇怪的符号，没有任何解释。这里发布的算法中，请大家帮忙。

 如果（键== A [MID]）返回中旬; //明白这一点，来自二进制搜索
如果（钥匙＆gt;在[MID]）{
  如果（对== 1）返回-1; //什么是对？它是作为一个功能ARG
  中等=中等+ Q; //现在这是什么？问再来一个函数ARG
  P =  -  q; //评论为p = FIB（K-4）
  Q = Q-P; // Q = FIB（K-5）
 信息} else //键＆LT; A [MID] {
  如果（Q == 0）返回-1;
  中期=中旬 -  q;
  温度= P  -  q;
  P = Q; // P = FIB（K-3）
  Q =温度; // Q = FIB（K-4）
  返回fibsearch（一个，键，中，P，Q）;
}
 

解决方案

我会努力让事情变得简短明了。比方说，你有一个排序的数组的的 A 的。此数组中有元素，在增加值。你必须找到这个阵内的特定元素。你想，这样的存取时间为的我的个数组元素中的分区这整个阵列为子阵列是不成正比的的我 。这意味着非衬垫更快方法。这里谈到斐波那契系列的帮助。之一斐波系列的最重要的性质是黄金比例的。您在此倒在斐波纳契数列（0,1,1,2,3,5,8,13,21，34 ...）索引分区排列为子阵列。

所以，你的阵列将被划分为区间如A [ 0 的] ... A [ 1 的]，A [ 1 的。 ..A [ 1 的]，A [ 1 的] ... A [ 2 的]，A [ 2 的] ... A [ 3 的]，A [ 3 的] ... A [ 5 的]，A [ 5 ] ... A [ 13 的]，A [ 13 的] ... A [ 21 的]，A [ 21 的] ... A [ 34 的]，等等。现在，因为数组排序，只要看一眼开始和结束的任何分区的元素会告诉你哪个分区的号码所在。所以，你遍历元素a [ 0 的]，A [ 1 的]，A [ 2 的]，A [ 3 的]，A [ 5 的]，A [ 8 的]，A [ 13 的]，A [ 21 的]，A [ 34 的] ...除非当前元素比你正在寻找的元素更大。现在，你确信你的电话号码这一当前元素，您访问的最后一个元素之间。

接下来，从A保持的元素[ F（I-1）的] ... A [ F（I）的]，在这里我是你的索引目前穿越; F（ X 的）是斐波纳契数列，并重复同样的程序，除非你发现你的元素。

如果您尝试<一href="http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence/360773#360773">calculate在这种方法的复杂性，这涉及到为O（日志（X））。这具有减少搜索所需的平均的时间的优点。

我相信你应该能够写下code自己。

Somebody please explain me the fibonacci search algorithm.

I have tried numerous resources around and searched a lot, but the algorithm is still unclear. Most of the resources described it in link with binary search, but I didn't understand 'em. I know fibonacci search algorithm is an extension of binary search, which I know quite well.

My books failed to explain as well.

I know about fibonacci numbers defined as F(n) = F(n-1) + F(n-2), so no need to explain that.

Updating the question by adding what exactly I didn't understand as @AnthonyLabarre said:

The book I'm using has strange symbols without any explanations. Posting the algo here, please help.

if(key == a[mid]) return mid; // understood this, comes from binary search
if(key > a[mid]) {
  if(p == 1) return -1; // What is p? It comes as a function arg
  mid = mid + q; //Now what's this q? Again comes a function arg
  p = p - q; // Commented as p=fib(k-4)
  q = q-p; // q = fib(k-5)
 } else // key < a[mid] {
  if(q == 0) return -1;
  mid = mid - q;
  temp = p - q;
  p = q; // p=fib(k-3)
  q = temp; // q = fib(k-4)
  return fibsearch(a, key, mid, p, q);
}

解决方案

I'll try to keep things short and clear. Let's say you have a sorted Array A. This array has elements in it, in increasing values. You must find a particular element inside this array. You want to partition this whole Array into sub arrays such that the access time to i th element in the Array is not directly proportional to i. That means a non liner quicker method. Here comes Fibonacci Series in help. One of the most important properties of Fibonacci series is the "golden ratio". You partition the array into sub-arrays at indexes which fall in fibonacci series (0,1,1,2,3,5,8,13,21, 34...).

So your array will be partitioned into intervals like A[0]...A[1], A[1]...A[1], A[1]...A[2], A[2]...A[3], A[3]...A[5], A[5]...A[13], A[13]...A[21], A[21]...A[34], and so on. Now since the array is sorted, just by looking at the starting and ending element of any partition will tell you which partition your number lies in. So, you traverse the elements A[0], A[1], A[2], A[3], A[5], A[8], A[13], A[21], A[34]... unless the current element is greater than the element you are looking for. Now you are sure that your number lies between this current element and the last element you visited.

Next, you keep the elements from A[f(i-1)]..A[f(i)], where i is the index you were currently traversing; f(x) is fibonacci series, and repeat the same procedure unless you find your element.

If you try to calculate the complexity of this approach, this comes to be O(log(x)). This has the advantage of reducing the "average" time required to search.

I believe you should be able to write down the code yourself.

这篇关于斐波那契搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！