斐波那契查找原理解析

点击(此处)折叠或打开

1. #include <iostream>
   
2. #include <assert.h>
   
3. 
   
4. #define MAXSIZE 13
   
5. 
   
6. void Fibonacci(int *f)
   
7. {
   
8.     f[0] = 1;
   
9.     f[1] = 1;
   
10. 
    
11.     for (int i = 2; i < MAXSIZE; i++)
    
12.     {
    
13.         f[i] = f[i - 1] + f[i - 2];
    
14.     }
    
15. }
    
16. 
    
17. int Fibonacci_Search(int *a, int n, int key)
    
18. {
    
19.     int low, high, mid;
    
20. 
    
21.     low = 1;
    
22.     high = n - 1;
    
23.  
    
24.     int k = 0;
    
25.     int F[MAXSIZE];
    
26.     Fibonacci(F);
    
27. 
    
28.      //这个查找n在斐波那契数列中的位置，为什么是F[k] - 1,而不是F[k]？
    
29.     while ( n > F[k] - 1 )
    
30.     {
    
31.         k++;
    
32.     }
    
33. 
    
34.     //这个地方，我发现被查找的数组a的长度不好计算，比如，我现在要查找31在数组a中的位置
    
35.     //那么，由于n = 13， 位于斐波那契数列中的第7个数（21）和第8个数（34）之间，所以k的
    
36.     //值为7，F[k] - 1就等于20，那么数组a的长度就需要是a[20]。换个数又变了，我不知道这个
    
37.     //应该怎么控制？
    
38.     for (int i = n; i < F[k] - 1; i++)
    
39.     {
    
40.         a[i] = a[high];
    
41.     }
    
42. 
    
43.         //还有这个判断，当键值小于a[mid]时，就在[low, F[k - 1] - 1]范围内查找
    
44.         //当键值大于a[mid]时，就在[F[k - 2] - 1]范围内查找，这个依据是什么？
    
45.     while(low <= high)
    
46.     {
    
47.         mid = low + F[k - 1] - 1;
    
48. 
    
49.         if ( key < a[mid] )
    
50.         {
    
51.             high = mid - 1;
    
52.             k = k - 1;
    
53.         }
    
54.         else if ( key > a[mid] )
    
55.         {
    
56.             low = mid + 1;
    
57.             k = k - 2;
    
58.         }
    
59.         else
    
60.         {
    
61.             if ( mid <= high )
    
62.             {
    
63.                 return mid;
    
64.             }
    
65.             else
    
66.                 return n;
    
67.         }
    
68.     }
    
69.     return -1;
    
70. }

解析：
首先要明确：如果一个有序表的元素个数为n,并且n正好是（某个斐波那契数 - 1），即n=F[k]-1时，才能用斐波那契查找法。 如果有序表的元素个n不等于（某个斐波那契数 - 1），即n≠F[k]-1，这时必须要将有序表的元素扩展到大于n的那个斐波那契数 - 1才行，这段代码：
for (int i = n; i < F[k] - 1; i++)
  {
  a[i] = a[high];
  }
便是这个作用。

下面回答
第一个问题：看完上面所述应该知道①是为什么了吧。 查找n在斐波那契数列中的位置，为什么是F[k] - 1,而不是F[k]，是因为能否用斐波那契查找法是由F[k]-1决定的，而不是F[k]。如果暂时不理解，继续看下面。

第 二个问题：a的长度其实很好估算，比如你定义了有10个元素的有序数组a[20]，n=10，那么n就位于8和13，即F[6]和F[7]之间，所以 k=7，此时数组a的元素个数要被扩充，为：F[7] - 1 = 12个； 再如你定义了一个b[20]，且b有12个元素，即n=12,那么很好办了，n = F[7]-1 = 12, 用不着扩充了； 又或者n=8或9或11，则它一定会被扩充到12； 再如你举的例子，n=13，最后得出n位于13和21，即F[7]和F[8]之间，此时k=8，那么F[8]-1 = 20,数组a就要有20个元素了。 所以，n = x（13<=x<=20）时，最后都要被扩充到20；类推，如果n=25呢，则数组a的元素个数肯定要被扩充到 34 - 1 = 33个（25位于21和34，即F[8]和F[9]之间，此时k=9，F[9]-1 = 33），所以，n = x（21<=x<=33）时，最后都要被扩充到33。也就是说，最后数组的元素个数一定是（某个斐波那契数 - 1），这就是一开始说的n与F[k]-1的关系。

第三个问题:对于二分查找，分割是从mid= (low+high)/2开始；而对于斐波那契查找，分割是从mid = low + F[k-1] - 1开始的； 通过上面知道了，数组a现在的元素个数为F[k]-1个，即数组长为F[k]-1，mid把数组分成了左右两部分， 左边的长度为：F[k-1] - 1， 那么右边的长度就为（数组长-左边的长度-1）， 即：（F[k]-1） - （F[k-1] - 1） = F[k] - F[k-1] - 1 = F[k-2] - 1。 
斐波那契查找的核心是：
  1）当key=a[mid]时，查找成功；
  2）当key<a[mid]时，新的查找范围是第low个到第mid-1个，此时范围个数为F[k-1] - 1个，即数组左边的长度，所以要在[low, F[k - 1] - 1]范围内查找；
  3）当key>a[mid]时，新的查找范围是第mid+1个到第high个，此时范围个数为F[k-2] - 1个，即数组右边的长度，所以要在[F[k - 2] - 1]范围内查找。