c - 斐波那契搜索

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。该数组中有元素，值递增。您必须在此数组中找到特定元素。您希望将整个 Array 划分为子数组，以便访问 Array 中第 i 个元素的时间与 i 。这意味着非线性更快的方法。来了Fibonacci Series在帮助中。斐波那契数列最重要的属性之一是“golden ratio”。您将数组按斐波那契数列(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[< em>1], A[2], A[3], A[5], A[ 8], A[13], A[21], A[34]...除非当前元素是大于您要查找的元素。现在您确定您的编号位于当前元素和您访问的最后一个元素之间。

接下来，您保留 A[f(i-1)]..A[f(i)] 中的元素，其中 i 是您的索引目前正在穿越； f(x) 是斐波那契数列，重复相同的过程，直到找到您的元素。

如果您尝试 calculate the complexity这种方法的复杂度为 O(log(x))。这具有减少搜索所需的“平均”时间的优点。

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