斐波那契搜索
有人请解释我的斐波那契搜索算法。
我已经尝试了很多资源并搜索了很多，但算法仍然不清楚。 大多数资源都将其描述为与二进制搜索相关联，但我不理解它们。 我知道斐波纳契搜索算法是二进制搜索的扩展，我很清楚。
我的书也没能解释。
我知道定义为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 = qp; // 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. 此数组中包含元素，值越来越大。 您必须在此数组中找到特定元素。 您希望将整个Array分区为子数组，以便对Array中第i个元素的访问时间与i不成正比。 这意味着一种非线性更快的方法。 Fibonacci系列有帮助。 Fibonacci系列最重要的特性之一是“ 黄金比例 ”。 您将数组分区为属于斐波纳契系列（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））。 这具有减少搜索所需的“平均”时间的优点。
我相信你应该能够自己写下代码。
评论中提供的参考文献是正确的，但我会尝试以不同的方式为您说出来。
它不断地将列表划分为子列表，其长度是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）的子列表一起使用。
由于斐波纳契数的性质，这些子列表中的任何一个也将具有斐波纳契数的长度，并且该过程将重复。 该算法的优点在于，在每个步骤中，列表中搜索的下一个地址将比正常二进制搜索的相同步骤更接近当前地址，这就是为什么该算法在慢速顺序访问媒体中具有优势，例如磁带机。