斐波那契搜索

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

我会尽量保持简短明了.比方说,你有一个排序的数组一个.此数组中包含元素,其值越来越大.您必须在此数组中找到特定元素.你想分区这整个数组子排列使得访问时间我日在数组元素是不成正比我.这意味着一种非线性更快的方法.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)).这具有减少搜索所需的"平均"时间的优点.

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