Fibonacci搜索

Question

谁能给我解释一下斐波那契搜索算法。

我尝试了很多资源，搜索了很多，但算法仍然不清楚。我知道斐波那契搜索算法是二进制搜索算法的一种扩展，我对它非常了解。

我的书也没能解释清楚。

我知道斐波那契数定义为F(n) = F(n-1) + F(n-2)，所以不需要解释。

通过添加我所不理解的内容来更新问题，就像@AnthonyLabarre所说的：

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

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);
}

Answer 1

我会尽量让事情简明扼要。假设你有一个排序数组A。这个数组中有元素，值在递增。您必须在此数组中找到一个特定的元素。您希望将整个数组划分为子数组，以便对数组中的i th元素的访问时间不与i成正比。这意味着一个非线性的更快的方法。Fibonacci Series在帮助中出现了。斐波那契级数最重要的性质之一是"golden ratio“。按照斐波那契数列(0,1,1,2,3,5,8,13,21，34...)的索引将数组划分为多个子数组。

因此，您的阵列将被划分为多个间隔，如A...A1、A1...A1、A1...A2、A2...A3、A3...A5、A5...A13、A13...A21、A21...A34等等。现在，由于数组已经排序，只需查看任何分区的开始和结束元素，就可以告诉您您的编号位于哪个分区。因此，您遍历元素A、A1、A2、A3、A5、A8、A13、A21、A34...除非当前元素大于您要查找的元素。现在您确定您的数字位于当前元素和您访问的最后一个元素之间。

接下来，保留Af(i-1)..Af(i)中的元素，其中i是您当前正在遍历的索引；f(x)是斐波那契级数，并重复相同的过程，除非找到您的元素。

如果你尝试对这种方法进行对数，结果是O( calculate the complexity (X))。这具有减少搜索所需的“平均”时间的优点。

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

Answer 2

评论中提供的参考资料是正确的，但我会尝试用不同的方式来表达它。

它不断地将列表划分为长度为Fibonacci序列(n = F(m))中的一个数字的子列表，然后搜索也在Fibonacci序列(F(m-1))中的倒数第二个索引。

因此，如果列表或子列表的长度为n项，其中n= F(m)，它将首先在F(m-1)处搜索，然后如果查找的值大于找到的值，它将处理从F(m-1)+1到F(M)的子列表，或者如果查找的值小于找到的值，它将处理从1到F(m-1)的子列表。

由于Fibonacci数的性质，这两个子列表的长度也将是Fibonacci数，并且该过程将重复。该算法的优点在于，在每个步骤中，在列表中搜索的下一个地址将比在正常的二进制搜索的相同步骤中更接近当前地址，这就是为什么该算法在诸如磁带驱动器之类的慢速顺序访问介质中具有优势。