斐波那契搜索

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

我尝试了很多资源并进行了很多搜索，但算法仍然不清楚。大多数资源都在与二分搜索的链接中描述了它，但我不明白它们。我知道斐波那契搜索算法是二分搜索的扩展，我对此非常了解。

我的书也未能解释。

我知道斐波那契数定义为 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);
}

我会尽量让事情简短明了。假设你有一个已排序的数组A。该数组中的元素的值递增。您必须在该数组中找到特定元素。您希望将整个数组划分为子数组，以便访问时间i数组中的第一个元素不成正比i。这意味着一种非线性的更快的方法。来了斐波那契数列 http://en.wikipedia.org/wiki/Fibonacci_number在帮助中。斐波那契数列最重要的属性之一是“黄金比例 http://en.wikipedia.org/wiki/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[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）是斐波那契数列，并重复相同的过程，除非找到您的元素。

如果你尝试计算复杂度 https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence/360773#360773采用这种方法，时间复杂度为 O(log(x))。这样做的优点是减少了搜索所需的“平均”时间。

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