斐波那契搜索

Question

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

我已经查阅了许多资源，也进行了大量的搜索，但是这个算法仍然不清楚。大部分的资源都将它与二分搜索联系在一起，但我并没有理解它们。我知道斐波那契搜索算法是二分搜索的扩展，而我对二分搜索非常了解。

我的书籍也没有详细解释。

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

- Nilesh

---

嗯，你到目前为止检查了什么，也许是这个？ - home

你没理解它只能证明它对你来说太复杂了，而不是书本有问题。学会承担责任！ - Blindy

你能具体指出你不理解的是什么吗？如果你懂二分查找，那我很难猜测。 - Anthony Labarre

p和q很可能是你在搜索关键字时所查找的数组a[]的上下标。 - Jens

也许学习http://www.seeingwithc.org/topic4html.html会让您更好地理解。它涵盖了线性搜索、二分搜索和斐波那契搜索。阅读整篇文章很有用，这样当您到达对斐波那契搜索的描述时，您就熟悉了作者的术语和编码风格。 - Jim Mischel

Answer 1

我会尽量简短明了地说明。假设你有一个已排序的数组A，其中元素按递增值排列。你必须在这个数组中找到一个特定的元素。你想将整个数组划分为子数组，使得访问数组中的第i个元素的时间不直接与i成正比，即使用一种非线性更快的方法。这时就需要斐波那契数列的帮助了。斐波那契数列最重要的性质之一是"黄金比例"。你可以在斐波那契数列(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)是斐波那契数列，并且除非找到你要的元素，否则重复相同的过程。

如果您尝试计算此方法的复杂度，它将为O(log(x))。这具有减少搜索所需的“平均”时间的优点。

我相信您应该能够自己编写代码。

- pr4n

Answer 2

给你提供的评论中的参考资料是正确的，但我会用不同的措辞来解释一下。

该算法将列表不断分成子列表，每个子列表的长度都是斐波那契数列中的一个数字（n=F(m)），然后在次后一个也在斐波那契数列中的索引（F(m-1)）处搜索。

因此，如果列表或子列表有n个项目，其中n=F(m)，它将首先在F(m-1)处搜索，然后，如果所寻找的值大于找到的值，则从F(m-1)+1到F(m)的子列表中进行处理；或者，如果所寻找的值小于找到的值，则使用1到F(m-1)的子列表进行处理。

由于斐波那契数列的性质，这些子列表中的任何一个长度也将是斐波那契数列中的一个数字，并且过程将重复。该算法的优点在于，在每一步中，搜索列表中的下一个地址将比普通二分查找的同一步骤更接近当前地址，这就是为什么该算法在慢速顺序存取媒体（如磁带驱动器）中具有优势的原因。

- Sam Skuce